Spectral Gap To Regular Graph Expansion

Claim/Theorem

Let \(G\) be a \(D\)-regular graph with second adjacency eigenvalue \(\lambda_2(G)\le \lambda < D\). Then the edge-Cheeger constant of \(G\) obeys

\[ h(G)\;\ge\;\frac{D-\lambda}{2}. \]

In particular, a constant spectral gap for a constant-degree regular graph gives a constant edge-expansion constant.

Dependencies

• None.

Conflicts/Gaps

• This is the standard regular-graph spectral-to-expansion step. It does not by itself treat the biregular incidence graph used in the quantum Tanner reduction.
• The statement is for the usual Cheeger constant h(G)=h_1(G). To get a local-expansion parameter for another graph family, one still needs a transfer step.

Sources

• 10.1007/BF02579166