Quasirandom Cayley graphs

DOI10.19086/DA.1294MaRDI QIDQ4645011zbMATH OpenOpenAlexWikidataFDO

Authors David Conlon, Yufei Zhao

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: We prove that the properties of having small discrepancy and having small second eigenvalue are equivalent in Cayley graphs, extending a result of Kohayakawa, R"odl, and Schacht, who treated the abelian case. The proof relies on Grothendieck's inequality. As a corollary, we also prove that a similar result holds in all vertex-transitive graphs.

Recommendations

• Discrepancy and eigenvalues of Cayley graphs
• Some graphs with small second eigenvalue
• Quasi-random hypergraphs revisited
• scientific article; zbMATH DE number 2159656
• Cayley graphs without a bounded eigenbasis

Cites work

• scientific article; zbMATH DE number 3124239 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• A new upper bound for the complex Grothendieck constant
• Absolutely summing operators in $ℒ_{p}$-spaces and their applications
• Discrepancy and eigenvalues of Cayley graphs
• Expander graphs and their applications
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Grothendieck-type inequalities in combinatorial optimization
• Grothendieck’s Theorem, past and present
• Hermitian matrices and graphs: Singular values and discrepancy
• Lifts, discrepancy and nearly optimal spectral gap
• Pseudo-random graphs
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Quasi-random graphs
• Quasirandom Groups
• Ramanujan graphs
• Sparse quasi-random graphs
• The Grothendieck constant is strictly smaller than Krivine's bound

Cited in

(5)

• Eigenvalues of Cayley graphs
• Outlaw distributions and locally decodable codes
• Failure of the trilinear operator space Grothendieck theorem
• Linear quasi-randomness of subsets of abelian groups and hypergraphs
• On quasi-Cayley graphs

This page was built for publication: Quasirandom Cayley graphs

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