Random Schreier graphs and expanders

Abstract

Let the group $G$ act transitively on the finite set $\Omega$, and let $S\subseteq G$ be closed under taking inverses. The Schreier graph $Sch(G\circlearrowleft \Omega ,S)$ is the graph with vertex set $\Omega$ and edge set $\{(\omega ,{\omega }^s):\omega \in \Omega ,s\in S\}$. In this paper, we show that random Schreier graphs on $C\log |\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.

8 pages (published version)

Cited by in corpus (2)

• The growth of abelian sections
• The diameter of random Schreier graphs