Discrepancy and eigenvalues of Cayley graphs

DOI10.1007/s10587-016-0302-xzbMath1413.05356arXiv1602.02291OpenAlexW3101242131WikidataQ101496266 ScholiaQ101496266MaRDI QIDQ2828826

Mathias Schacht, Yoshiharu Kohayakawa, Vojtěch Rödl

Publication date: 26 October 2016

Published in: Czechoslovak Mathematical Journal (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.02291

zbMATH Keywords

Cayley graphdiscrepancysecond eigenvaluesparse graphquasi-random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Density (toughness, etc.) (05C42)

Related Items

Eigenvalues of Cayley graphs, Quasirandom Cayley graphs, Linear quasi-randomness of subsets of abelian groups and hypergraphs, Outlaw distributions and locally decodable codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Spectral partitioning works: planar graphs and finite element meshes
• Lifts, discrepancy and nearly optimal spectral gap
• On universality of graphs with uniformly distributed edges
• Explicit construction of linear sized tolerant networks
• The number of submatrices of a given type in a Hadamard matrix and related results
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Spectra of Cayley graphs
• Spectra of graphs with transitive groups
• Sparse quasi-random graphs
• Embedding graphs with bounded degree in sparse pseudorandom graphs
• Extremal results in sparse pseudorandom graphs
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Explicit Concentrators from Generalized N-Gons
• Regular pairs in sparse random graphs I
• An r-Dimensional Quadratic Placement Algorithm
• Lower Bounds for the Partitioning of Graphs
• Quasi-random graphs