Discrepancy and eigenvalues of Cayley graphs

DOI10.1007/S10587-016-0302-XMaRDI QIDQ2828826zbMATH OpenOpenAlexWikidataFDO

Authors Yoshiharu Kohayakawa, Vojtěch Rödl, M. Schacht

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, http://hdl.handle.net/10338.dmlcz/145881

zbMATH Keywords

Cayley graphdiscrepancyquasi-random graphsecond eigenvaluesparse graph

Mathematics Subject Classification ID

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

Abstract: We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This positively answers a question of Chung and Graham ["Sparse quasi-random graphs", Combinatorica 22 (2002), no. 2, 217-244] for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.

Recommendations

• scientific article; zbMATH DE number 2159656
• Random Cayley graphs and expanders
• scientific article; zbMATH DE number 475373
• On subgraphs of random Cayley sum graphs
• A Spectral Turán Theorem
• Pseudo-random graphs
• Hamilton cycles in random subgraphs of pseudo-random graphs
• Counting sets with small sumset, and the clique number of random Cayley graphs
• scientific article; zbMATH DE number 1405807

Cites work

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

Cited in

(5)

• Eigenvalues of Cayley graphs
• Closed walks and eigenvalues of abelian Cayley graphs
• Outlaw distributions and locally decodable codes
• Quasirandom Cayley graphs
• Linear quasi-randomness of subsets of abelian groups and hypergraphs

This page was built for publication: Discrepancy and eigenvalues of Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828826)