Local Expansion of Symmetrical Graphs

DOI10.1017/S0963548300000031zbMath0792.05064MaRDI QIDQ4291181

László Babai, Mario Szegedy

Publication date: 14 July 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

automorphism groupdiametervertex-transitive graphedge-transitiveexpansion rate

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph theory (05C99)

Related Items

Percolation on finite graphs and isoperimetric inequalities., Percolation and isoperimetry on roughly transitive graphs, The isoperimetric number of the incidence graph of \(\operatorname{PG}(n,q)\), Lifshitz asymptotics for percolation Hamiltonians, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, On geometric properties of directed vertex-symmetric graphs, Finite groups of uniform logarithmic diameter., On Small Separations in Cayley and Vertex Transitive Graphs, Robust locally testable codes and products of codes, On the treewidth of Hanoi graphs, Lattices in graphs with polynomial growth, Small separations in vertex-transitive graphs

Cites Work

• Non-deterministic exponential time has two-prover interactive protocols
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Isoperimetric inequalities and fractional set systems
• Isoperimetric inequalities and Markov chains
• Ramanujan graphs
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• A short proof for a theorem of Harper about Hamming-spheres
• A note on the edges of the n-cube
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Arc transitive covering digraphs and their eigenvalues
• A Survey on Spectra of infinite Graphs
• Optimal numberings and isoperimetric problems on graphs
• Connectivity of transitive graphs
• Unnamed Item
• Unnamed Item