Recursive Construction for 3-Regular Expanders

We present an algorithm which in n3(log n)3 time constructs a 3- regular expander graph on n vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of length s = [c log n] decreases (for some fixed absolute constant c). When we reach a local minimum in the number of cycles of length s the graph is an expander. The proof is completely elementary, we use only the basic results about the eigenvalues and eigenvectors of symmetric matrices.

Authors

• Miklós Ajtai

Keywords

• Graph theory
• Eigenvalues and eigenfunctions
• Symmetric matrices
• Bipartite graph
• Computer science
• Sorting
• Computational complexity
• Computational modeling
• Computer simulation
• Upper bound
• Recursive Construction
• Sufficiently Large
• Path Length
• Probability Of Events
• Cycle Length
• Largest Eigenvalue
• Small Constant
• Simple Cycle
• Cycling Of Elements
• Lemma States
• Explicit Construction
• Pair Of Edges
• Random Path
• Graph Changes
• Absolute Constant
• Critical Edge
• Family Of Graphs