Random Schreier graphs and expanders

DOI10.1007/S10801-022-01136-ZMaRDI QIDQ2082534zbMATH OpenOpenAlexFDO

Authors Luca Sabatini

Publication date 4 October 2022

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

expander graphsnilpotent groupsSchreier graphs

Mathematics Subject Classification ID

Expander graphs (05C48) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in group theory (20P05)

Abstract: Let the group $G$ act transitively on the finite set $Omega$, and let $SsubseteqG$ be closed under taking inverses. The Schreier graph $Sch(GcirclearrowleftOmega,S)$ is the graph with vertex set $Omega$ and edge set $(omega,omeg{a}^s):omegainOmega,sinS$. In this paper, we show that random Schreier graphs on $Clog|Omega|$ elements exhibit a (two-sided) spectral gap with high probability, magnifying a well known theorem of Alon and Roichman for Cayley graphs. On the other hand, depending on the particular action of $G$ on $Omega$, we give a lower bound on the number of elements which are necessary to provide a spectral gap. We use this method to estimate the spectral gap when $G$ is nilpotent.

Recommendations

• scientific article; zbMATH DE number 1405807
• Random Cayley graphs and expanders
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• scientific article; zbMATH DE number 475373
• scientific article; zbMATH DE number 2159656

Cites work

• Asymptotic enumeration of vertex-transitive graphs of fixed valency
• Asymptotic growth of finite groups
• Expander graphs and their applications
• Expansion of random graphs: new proofs, new results
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• scientific article; zbMATH DE number 475380 (Why is no real title available?)
• scientific article; zbMATH DE number 5272192 (Why is no real title available?)
• Nilprogressions and groups with moderate growth
• Random Cayley graphs and expanders
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• Spectral estimates for abelian Cayley graphs
• Strong converse for identification via quantum channels

Cited in

(12)

• Fast scramblers, horizons and expander graphs
• On invariant Schreier structures
• scientific article; zbMATH DE number 2128183 (Why is no real title available?)
• Strong approximation in random towers of graphs.
• scientific article; zbMATH DE number 1405807 (Why is no real title available?)
• A spectral strong approximation theorem for measure-preserving actions
• Expanders via Random Spanning Trees
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Mini-workshop: Growth and expansion in groups. Abstracts from the mini-workshop held April 7--12, 2024
• Random Schreier graphs as expanders
• The diameter of random Schreier graphs
• Random Schreier graphs as expanders

Describes a project that uses

Uses Software

• GAP

This page was built for publication: Random Schreier graphs and expanders

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