Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
From MaRDI portal
Publication:5436978
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
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
This page was built for publication: Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales