Plünnecke graph

A finite directed graph with layers $V_0,\dots ,V_n$ and edges only to the next layer is a Plünnecke graph when every edge $u\to v$ permits both commutation matchings. The successors of $v$ inject into the successors of $u$ through edges to the original successors; the predecessors of $u$ inject into those of $v$ through edges from the original predecessors. These conditions formalize interchanging adjacent summands in an additive graph. They persist on channels consisting of paths between prescribed endpoint sets.

A minimum-weight set meeting every bottom-to-top path can be chosen entirely in the endpoint layers. The local step is a three-layer channel whose middle layer is a minimum cut. Replacing middle subsets by their successors or predecessors gives expansion inequalities. Sorting middle vertices by incoming degree and top vertices by their largest predecessor degree gives one edge-count inequality; reversing the graph gives the opposite inequality. Equality forces the bottom layer to have the same weight as the middle cut. Replacing the highest intermediate portion of a minimum cut by this bottom layer repeatedly proves the assertion.

This is the smallest ratio of the size of a $k$-step image to the size of its nonempty starting set in the bottom layer. For a Plünnecke graph, the roots $D_k^{1/k}$ are nonincreasing. The minimum, rather than just the image of the whole layer, is essential.