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 .

Articles by others on the same topic (0)

There are currently no matching articles.