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!