Regular Graph Expansion To Incidence Expansion¶

Claim/Theorem¶

This node is a graph-internal corollary schema. Let \(G\) be a \(D\)-regular graph on \(n\) vertices, and let \(I(G)\) be its vertex-edge incidence graph with left vertices the edges of \(G\) and right vertices the vertices of \(G\). If \(h_\varepsilon(G)\ge \alpha_G\), then

\[ h_{\varepsilon_I}(I(G))\;\ge\;\frac{\alpha_G}{D+1}, \qquad \varepsilon_I\;=\;\frac{\varepsilon}{D/2+1}. \]

So any local-expansion bound for the regular graph \(G\) induces a local-expansion bound for its incidence graph.

The proof is a direct counting argument. For a subset \(W=S\cup U\) of the incidence graph, write \(U\) for the chosen graph vertices and \(S\) for the chosen graph edges. Edges of \(S\) not incident to \(U\) contribute boundary 2 each, while the remaining boundary is at least the edge boundary of \(U\) in \(G\). Since at most \(D|U|\) graph edges are incident to \(U\), one gets

\[ |\partial_{I(G)}W| \;\ge\; \alpha_G|U|+2\,|S\setminus \operatorname{Inc}(U)|, \]

and

\[ |W| \;\le\; (D+1)|U|+|S\setminus \operatorname{Inc}(U)|. \]

Taking the ratio yields the stated lower bound.

Dependencies¶

[[spectral-gap-to-regular-graph-expansion.md]]

Conflicts/Gaps¶

This is a corollary schema rather than a named theorem from a source paper.
The argument uses the ordinary incidence graph of a regular graph. Applying it to a concrete code family still requires identifying that incidence graph inside the code construction.
The expansion constant degrades by the factor D+1, which is harmless for constant-degree constructions but would be weak in growing-degree families.

Sources¶

10.1007/BF02579166
10.48550/arXiv.2109.14599