Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

DOI10.1002/rsa.20177zbMath1130.05030OpenAlexW4243231294MaRDI QIDQ5436978

Demetres Christofides, Klas Markström

Publication date: 18 January 2008

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20177

zbMATH Keywords

Cayley graphsexpandersconcentration inequalities

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Random graphs (graph-theoretic aspects) (05C80) Ordinary representations and characters (20C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (16)

Eigenvalues of Cayley graphs ⋮ On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon–Roichman Graphs ⋮ Random Latin square graphs ⋮ EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES ⋮ Time-uniform Chernoff bounds via nonnegative supermartingales ⋮ Geometry of random Cayley graphs of abelian groups ⋮ On the spectra of general random mixed graphs ⋮ Comparison of Metric Spectral Gaps ⋮ Concentration inequalities for matrix martingales in continuous time ⋮ User-friendly tail bounds for sums of random matrices ⋮ Ranking and Sparsifying a Connection Graph ⋮ The chromatic number of random Cayley graphs ⋮ The spectra of multiplicative attribute graphs ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ Random Schreier graphs and expanders ⋮ Loose laplacian spectra of random hypergraphs

Cites Work

• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales