The diameter of random Schreier graphs

Abstract

We give a combinatorial proof of the following theorem. Let $G$ be any finite group acting transitively on a set of cardinality $n$. If $S\subseteq G$ is a random set of size $k$, with $k\ge (\log n{)}^{1+\epsilon }$ for some $\epsilon >0$, then the diameter of the corresponding Schreier graph is $O({\log }_{k}n)$ with high probability. Except for the implicit constant, this result is the best possible.

10 pages, to appear in European J. Combin

References in corpus (2)

• Random Schreier graphs and expanders
• On directed and undirected diameters of vertex-transitive graphs