Small Lifts of Expander Graphs are Expanding
summary
Claim: random two-lifts (and more generally k‑shift lifts) preserve expansion: new eigenvalues of the lift have spectral radius bounded by about O(Lambda) where Lambda is the largest nontrivial eigenvalue of the base graph, with high probability over the random choice of permutations. Key tools: 2‑lifts correspond to edge signings, so the problem reduces to bounding the spectral radius of a signed adjacency matrix; dyadic decomposition plus expander‑mixing style bounds remove previous log losses. Limitation: dependence on Lambda is necessary and the result is not yet a deterministic construction.
AI-written summary · about