Cayley graphs without a bounded eigenbasis

DOI10.1093/IMRN/RNAA298MaRDI QIDQ5071156zbMATH OpenOpenAlexFDO

Authors Ashwin Sah, Mehtaab Sawhney, Yufei Zhao

Publication date 20 April 2022

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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

zbMATH Keywords

eigenvalues of Cayley graphsmall-set expanders

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Expander graphs (05C48) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Does every $n$-vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are $O(1/sqrtn)$? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every $n$-vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all $O(sqrtlogn/n)$, and that this bound is nearly best possible. Our investigation is motivated by a question of Assaf Naor, who proved that random abelian Cayley graphs are small-set expanders, extending a classic result of Alon--Roichman. His proof relies on the existence of a bounded eigenbasis for abelian Cayley graphs, which we now know cannot hold for general groups. On the other hand, we navigate around this obstruction and extend Naor's result to nonabelian groups.

Recommendations

• scientific article; zbMATH DE number 2159656
• scientific article; zbMATH DE number 475373
• Random Cayley graphs and expanders
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• scientific article; zbMATH DE number 782054

Cited in

(6)

• On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs
• Quasirandom Cayley graphs
• Cayley graphs that have a quantum ergodic eigenbasis
• Quantum unique ergodicity for Cayley graphs of quasirandom groups
• Geometry of random Cayley graphs of abelian groups
• Delocalized eigenvectors of transitive graphs and beyond

This page was built for publication: Cayley graphs without a bounded eigenbasis

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