Squaring and zig-zag iteration yields bounded-degree expanders

ID: squaring-and-zig-zag-iteration-yields-bounded-degree-expanders

Choose and a fixed -regular graph on vertices with absolute nonconstant eigenvalues at most . Start with the loop-inclusive complete graph on vertices and iterate . The degree stays , vertex counts are , and . Since , all . The spectral cut bound gives multiplicity-counted edge expansion at least . Removing loops and merging parallel edges loses at most a factor , producing simple expander graphs with maximum degree and edge expansion at least .

New to topics? Read the docs here!