# The diameter of random Schreier graphs

Daniele Dona  Hun-Ren Alfréd Rényi Institute of Mathematics, Budapest, Hungary
<EMAIL_ADDRESS>and  Luca Sabatini  Luca Sabatini, Queen’s University Belfast
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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\geq(\log n)^{1+\varepsilon}$ for some
$\varepsilon>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.

###### Key words and phrases:

Random graphs, Schreier graphs, diameter.

###### 2020 Mathematics Subject Classification:

Primary: 05C89, 20F69.

##  1\. Introduction

Let $G$ be a finite group acting transitively on a set $\Omega$, and let
$S\subseteq G$. The Schreier graph
$\Gamma=\mathop{\mathrm{Sch}}(G\circlearrowleft\Omega,S)$ is the directed
multigraph with vertex set $V(\Gamma)=\Omega$, and the edges are the pairs
$(\omega,\omega^{s})$ for every $\omega\in\Omega$ and $s\in S$. This is a
natural generalization of Cayley graphs, which arise when $G$ is a regular
permutation group on $\Omega$, and we can identify $\Omega$ with $G$. The
general setting is much wilder, as there is no natural action of $G$ on
$V(\Gamma)$ that preserves the graph structure. For example, it is well known
that every regular graph of even degree is a Schreier graph over
$\mathop{\mathrm{Sym}}(\Omega)$ [9].
In this paper, we are interested in the diameter of random Schreier graphs,
where by random we mean that the action of $G$ on $\Omega$ is fixed, and a
multiset $S\subseteq G$ of size $k$ is chosen uniformly at random. The value
of $k$ is allowed to depend on the size of $\Omega$, which in turn is going to
infinity. It is clear that the results have to depend on the particular group
$G$ and action, and on how large $k$ is with respect to the cardinalities of
$G$ and $\Omega$. For specific “nice” actions and bounded $k$, strong results
have been obtained in [4, 8, 5, 7]. For example, for
$\mathop{\mathrm{Sym}}(\Omega)$ in its natural action on $r$-uples ($r$
fixed), and for any fixed $k\geq 2$, the symmetrization of the resulting
Schreier graph is a $2k$-regular expander graph with high probability [8]. The
situation turned out to be quite different for an arbitrary “bad” action.
Since $\Gamma$ is connected if and only if the subgroup generated by $S$ is
transitive, it is necessary for $k$ to grow with the size of $\Omega$: for a
regular permutation group, $k$ has to be at least the minimal number of
generators.
Let $n$ be the cardinality of $\Omega$. For $k=\Omega(\log n)$, a logarithmic
bound $O(\log n)$ for the diameter of a random Cayley graph was first given by
Alon, Barak and Manber [1] using a combinatorial method. Nowadays, we know
that $\Omega(\log n)$ random elements are always sufficient to get an expander
with high probability [2, 15]. For slightly larger $k$, Roichman [14, Theorem
5.6] proved the following better diameter bound for Cayley graphs:

######  Theorem (Roichman).

Let $\varepsilon>0$, and let $G$ be any group of cardinality $n$. Let
$k=\lfloor(\log n)^{1+\varepsilon}\rfloor$, and let $S\subseteq G$ be a random
set of $k$ elements. Then

$\mathop{\mathrm{diam}}(\>\mathop{\mathrm{Cay}}(G,S)\>)\>\leq\>2(1+\varepsilon^{-1})\>\frac{\log
n}{\log k}$

with high probability.

Roichman’s theorem is sharp in a number of directions. First, it is clear that
a bound of the type $O(\log_{k}n)$ is the best possible for the diameter of a
$k$-regular graph on $n$ vertices. Second, it is not hard to see [14,
Proposition 5.7] that, for an abelian group of order $n$, $(\log
n)^{1+\varepsilon}$ elements are necessary to get such a bound $O(\log_{k}n)$.
Third, a constant of the type $O(\varepsilon^{-1})$ is the best possible for
small $\varepsilon$.
It is natural to ask for a generalization to arbitrary transitive groups. It
is remarkable that Roichman obtains his theorem by studying the mixing time of
random random walks (see also [6]). As well as being a tortuous road to give
an estimate for the diameter, it is not clear whether these ideas can be
applied in the general framework: they use many distinguished properties of
Cayley graphs, in particular their vertex-transitivity. Moreover, while it is
natural that abelian groups represent the worst case for Cayley graphs, this
is not obvious in general: an abelian group only provides vertex-transitive
Schreier graphs, which is a very desirable property when bounding the directed
diameter [3, 16]. In this paper, we come back to combinatorics. We provide a
direct proof of the following theorem, which settles the question of the
diameter of random Schreier graphs up to the multiplicative constant.

######  Theorem 1.1.

For every $\varepsilon>0$ there exists $C>0$ such that the following holds.
Let $\Omega$ be a set of cardinality $n$, and let $G$ be any finite group
acting transitively on $\Omega$. Let $k\geq(\log n)^{1+\varepsilon}$, and let
$S\subseteq G$ be a random multiset of $k$ elements. Then

$\mathop{\mathrm{diam}}(\>\mathop{\mathrm{Sch}}(G\circlearrowleft\Omega,S)\>)\>\leq\>C\>\frac{\log
n}{\log k}$

with high probability.

The diameter of a multigraph equals the diameter of the underlying graph, so
Theorem 1.1 implies the corresponding version for random sets.111The
distribution of random $k$-multisets is not the same as the distribution of
random $k$-sets, but this is only a minor technical inconvenience. We
highlight the validity for all large $k$, for example $k=\lfloor
n^{\delta}\rfloor$ with fixed $\delta>0$. In this case, we obtain that the
diameter is bounded by $C\delta^{-1}$, where $C$ is an absolute constant.

##  2\. Growth in random Schreier graphs

The proof of Theorem 1.1 is inspired by the more modern philosophy of growth
in groups. We refer the reader to the beautiful survey [10] for an
introduction to this vibrant subject, and to [13] for some generalizations in
the context of group actions (i.e. Schreier graphs). We believe that this
article is yet another demonstration of the power of these techniques. We
follow two main steps, which we explain in Propositions 2.1 and 2.2 below.
When $A\subseteq G$ and $t\in\mathbb{N}$, we write
$A^{t}=\\{a_{1}\cdot\ldots\cdot a_{t}:a_{1},\ldots,a_{t}\in A\\}$ for the set
of products of $t$ elements of $A$. If $\omega\in\Omega$, we write
$\mathcal{S}_{A}(\omega,t)$ to denote the sphere of radius $t$ in
$\mathop{\mathrm{Sch}}(G\circlearrowleft\Omega,A)$ and centered in $\omega$,
i.e.

$\mathcal{S}_{A}(\omega,t)\>=\>\omega^{(A^{t})}\>=\>\\{\omega^{g}:g\in
A^{t}\\}.$

We remark that $\mathcal{S}_{A}(\omega,t)=\mathcal{S}_{A^{t}}(\omega,1)$ for
all $t\in\mathbb{N}$. Moreover,

(2.1)
$\mathop{\mathrm{diam}}(\>\mathop{\mathrm{Sch}}(G\circlearrowleft\Omega,A)\>)\>=\>\max_{\omega\in\Omega}\min\\{t\in\mathbb{N}:\mathcal{S}_{A}(\omega,t)=\Omega\\}.$

We write $A\sim\mu_{G}(k)$ to say that $A\subseteq G$ is a random multiset of
size $k$ chosen with the uniform distribution.

######  Proposition 2.1 (Growth).

For every $\varepsilon>0$ there exists $C>0$ such that the following holds.
Let $G$ be any finite group acting transitively on a set $\Omega$ with
$|\Omega|=n$, and let $k\geq(\log n)^{1+\varepsilon}$. Fix $\omega\in\Omega$.
Then, for $A\sim\mu_{G}(k)$, we have

$\left|\mathcal{S}_{A}\left(\omega,\left\lfloor
C\log_{k}n\right\rfloor\right)\right|\>\geq\>\frac{n}{k^{\varepsilon/2}}$

with high probability.

At this stage, we stress that the multiplicative gap between
$|\mathcal{S}_{A}(\omega,t)|$ and $|\Omega|$ depends on $k$ (and is
unbounded). Once we have a large sphere, we bound the diameter with the help
of a few more random elements.

######  Proposition 2.2 (Diameter bound).

Let $\delta>0$. Suppose that, for some $\omega\in\Omega$, for
$A\sim\mu_{G}(k)$ we have $|\mathcal{S}_{A}(\omega,t)|\geq|\Omega|/k^{\delta}$
with high probability. Then, for $B\sim\mu_{G}(2k+8k^{\delta}\log n)$, we have

$\mathop{\mathrm{diam}}(\>\mathop{\mathrm{Sch}}(G\circlearrowleft\Omega,B)\>)\>\leq\>2t+2$

with high probability.

In order to use Proposition 2.2 to prove Theorem 1.1, it is important to
notice that $k^{\delta}\log n$ is comparable with $k$, if $k$ is larger than
$(\log n)^{1+\varepsilon}$ and $\delta$ is small enough with respect to
$\varepsilon$. In the remaining part of this section we prove Proposition 2.1,
while Proposition 2.2 and Theorem 1.1 will be proven in Section 3.

###  2.1. Random conjugates

Let $X,Y\subseteq\Omega$, and let $g\in G$ be random. It is intuitive that, if
$\Omega$ is large, then a random conjugate $X^{g}$ of $X$ intersects $Y$ in a
few points with high probability. This is the content of the following lemma.

######  Lemma 2.3.

Let $G$ be any finite group acting transitively on a set $\Omega$. Let $r,s>0$
and $X,Y\subseteq\Omega$. Suppose that for at least $|G|/s$ of the elements
$g\in G$ we have $|X^{g}\cap Y|\geq r$. Then $|\Omega|\leq\frac{|X||Y|s}{r}$.

###### Proof.

Let $t$ be the cardinality of a stabilizer, namely $t=|G|/|\Omega|$. Let $y\in
Y$. For each $x\in X$, there are precisely $t$ elements $g\in G$ such that
$y=x^{g}$. Therefore, each element of $Y$ lies in the same number $t|X|$ of
translates $(X^{g})_{g\in G}$, and so

$|\\{(y,g)\in Y\times G:y\in X^{g}\\}|\>=\>t|X||Y|.$

On the other hand, we have

$|\\{(y,g)\in Y\times G:y\in X^{g}\\}|\>=\>\sum_{g\in G}|X^{g}\cap
Y|\>\geq\>\frac{|G|r}{s}.$

The proof follows. ∎

We can read Lemma 2.3 as follows. If

(2.2) $|Y|\><\>\frac{|\Omega|r}{|X|s},$

then there are at least $|G|(1-s^{-1})$ elements $g\in G$ such that
$|X^{g}\cap Y|<r$. The next key result exploits this fact to give a glimpse of
growth. For a random distribution $\mu$, we write $\mathbb{P}_{\mu}$ to denote
the probability of a certain event with respect to $\mu$.

######  Lemma 2.4 (One-step growth).

Let $G$ be any finite group acting transitively on a set $\Omega$. Let $r,s>0$
and $X\subseteq\Omega$, and let $k$ be an integer such that

(2.3) $|\Omega|\>\geq\>\frac{ks|X|^{2}}{r}.$

Then, for $A\sim\mu_{G}(k)$, we have

$\mathbb{P}_{\mu_{G}(k)}\left(\>\left|X^{A}\right|\geq
k\left(|X|-r\right)\>\right)\>\geq\>\left(1-\frac{1}{s}\right)^{k}.$

###### Proof.

We work by induction on $k$, the case $k=1$ being trivial. Let $k\geq 2$, and
suppose that (2.3) holds. By induction, for $A^{\prime}\sim\mu_{G}(k-1)$, we
have

(2.4)
$\mathbb{P}_{\mu_{G}(k-1)}\left(\left|X^{A^{\prime}}\right|\>\geq\>(k-1)\left(|X|-r\right)\right)\>\geq\>\left(1-\frac{1}{s}\right)^{k-1}.$

For any evaluation $(g_{1},\ldots,g_{k-1})$ of $A^{\prime}$, we set

$Y\>=\>X^{\\{g_{1},\ldots,g_{k-1}\\}}\>=\>\bigcup_{i=1}^{k-1}X^{g_{i}}.$

Certainly $|Y|<k|X|$, and so it is easy to check that (2.2) follows from
(2.3). Take a random $g_{k}\in G$, which is the same as considering
$\\{g_{k}\\}\sim\mu_{G}(1)$. We obtain

(2.5) $\mathbb{P}_{\mu_{G}(1)}\biggl{(}|X^{g_{k}}\cup
Y|\>\geq\>|X|+|Y|-r\biggr{)}\>\geq\>1-\frac{1}{s}.$

Since $A^{\prime}\sim\mu_{G}(k-1)$ and $\\{g_{k}\\}\sim\mu_{G}(1)$, we have
$A=A^{\prime}\cup\\{g_{k}\\}\sim\mu_{G}(k)$. Putting together (2.4) and (2.5),
with probability at least $(1-s^{-1})^{k}$, we have

$\displaystyle\left|X^{A}\right|$ $\displaystyle\>=\>\left|X^{A^{\prime}}\cup
X^{g_{k}}\right|$ $\displaystyle\>\geq\>(k-1)\left(|X|-r\right)+|X|-r$
$\displaystyle\>=\>|X|k-rk\>$

as desired. ∎

For the convenience of the reader, we state a special version of Lemma 2.4,
which is the one we will use later.

######  Corollary 2.5.

Let $d\geq 2$. Let $G$ be any finite group acting transitively on a set
$\Omega$. Let $X\subseteq\Omega$, and let $k\geq 4$ be an integer such that

(2.6) $|X|\>\leq\>\frac{|\Omega|}{k^{d}}.$

Then, for $A\sim\mu_{G}(k)$, we have

$\mathbb{P}_{\mu_{G}(k)}\left(\>\left|X^{A}\right|\geq\sqrt{k}|X|\>\right)\>\geq\>\left(1-\frac{2}{k^{d-1}}\right)^{k}.$

###### Proof.

Apply Lemma 2.4, with

$\displaystyle r$ $\displaystyle=|X|\left(1-\frac{1}{\sqrt{k}}\right),$
$\displaystyle s$ $\displaystyle=\frac{k^{d-1}}{2},$

and note that $r\geq|X|/2$ by our choice of $k$. ∎

###  2.2. Growth of spheres

We start estimating the size of random spheres. To do so, we divide the random
set $A$ into a bounded number of pieces of comparable size, and use the
trivial observation that, if $A_{1},A_{2}\subseteq A$, then
$A_{1}A_{2}\subseteq A^{2}$. This allows to create apparently new random
elements while we are growing.

######  Lemma 2.6.

For every $\varepsilon\in(0,1)$ there exists $C>0$ such that the following
holds. Let $G$ be any finite group acting transitively on a set $\Omega$ with
$|\Omega|=n$, and let $k\geq(\log n)^{1+\varepsilon}$. Fix $\omega\in\Omega$.
Then, for $A\sim\mu_{G}(k)$, we have

$\left|\mathcal{S}_{A}\left(\omega,\left\lfloor
C\log_{k}n\right\rfloor\right)\right|\>\geq\>\frac{n}{k^{2/\varepsilon}}$

with high probability.

###### Proof.

Let $D,h\geq 1$ be positive integers, to be chosen later, such that $Dh\leq
k$. We can rewrite $A\subseteq G$ as

$\displaystyle A$ $\displaystyle=A_{1}\cup\ldots\cup A_{D}\cup A^{\prime},$
$\displaystyle A_{i}$ $\displaystyle\sim\mu_{G}(h),$ $\displaystyle
A^{\prime}$ $\displaystyle\sim\mu_{G}(k-Dh),$

where $A_{1},\ldots,A_{D},A^{\prime}$ are disjoint as multisets. Remark that
$\prod_{i=1}^{D}A_{i}\subseteq A^{D}$, so we can effectively work with each
$A_{i}$ independently, and discard $A^{\prime}$. We apply Corollary 2.5
iteratively, choosing $X=\mathcal{S}_{A_{1}\cdot\ldots\cdot
A_{i-1}}(\omega,1)$, $A_{i}\sim\mu_{G}(h)$, $d=2\varepsilon^{-1}$, starting
with $X=\\{\omega\\}$ for $i=1$. Observe that
$X^{A_{i}}=\mathcal{S}_{A_{1}\cdot\ldots\cdot A_{i}}(\omega,1)$ at each step.
If (2.6) is true for all $1\leq i<D$, then

$|\mathcal{S}_{A_{1}\cdot\ldots\cdot A_{D}}(\omega,1)|\>\geq\>h^{D/2}$

with positive probability. It follows that, if $h^{D/2}>n$, then (2.6) must
fail at some $i<D$. This means that

$|\mathcal{S}_{A}(\omega,D)|\>\geq\>|\mathcal{S}_{A_{1}\cdot\ldots\cdot
A_{D}}(\omega,1)|>\frac{n}{h^{2/\varepsilon}}\>\geq\>\frac{n}{k^{2/\varepsilon}}$

with probability at least

(2.7)
$\left(1-\frac{2}{h^{2\varepsilon^{-1}}}\right)^{hD}\>\geq\>1-\frac{2D}{h^{2\varepsilon^{-1}-1}}.$

Finally, it is a matter of routine to check that, for some
$C(\varepsilon)=O(\varepsilon^{-1})$, the choice

$\displaystyle D$ $\displaystyle=\left\lfloor\frac{C\log n}{\log
k}\right\rfloor,$ $\displaystyle h$
$\displaystyle=\left\lfloor\frac{k}{D}\right\rfloor,$

does the job. We now omit the floor notation since it is not crucial.
To check that $h^{D/2}>n$, some computations show that this is equivalent to

(2.8) $\left(\frac{k\log k}{C\log n}\right)^{C}\>>\>k^{2}.$

From the hypotheses we have $\log n\leq k^{1/(1+\varepsilon)}$, so an
exponential portion of $k$ survives on the left side of (2.8). When $n$ and so
$k$ are sufficiently large, the existence of a good $C=O(\varepsilon^{-1})$ is
assured. Similarly, the probability in (2.7) is bounded from below by

$1-\frac{2D}{h^{2\varepsilon^{-1}-1}}\>\geq\>1-\left(\frac{2C\log n}{\log
k}\right)\left(\frac{C\log n}{k\log k}\right)^{2\varepsilon^{-1}-1}.$

Since $k\geq(\log n)^{1+\varepsilon}$, we have

$\left(\frac{2C\log n}{\log k}\right)\left(\frac{C\log n}{k\log
k}\right)^{2\varepsilon^{-1}-1}\>\leq\>\frac{2C^{2\varepsilon^{-1}}}{(\log
n)^{1-\varepsilon}},$

which is going to zero as $n$ grows. ∎

To obtain Proposition 2.1 from Lemma 2.6, we have to close the gap from
$k^{2/\varepsilon}$ to $k^{\varepsilon/2}$. We apply Corollary 2.5 a few more
times.

###### Proof of Proposition 2.1.

It is sufficient to prove the result for small $\varepsilon$. Moreover, we
omit the floor notation since it is not crucial. Let
$C_{2}=6\varepsilon^{-3}$. For $n$ (and thus $k$) large enough, we have
$k\geq\frac{k}{2}+C_{2}k^{\varepsilon^{2}}$, so we can rewrite $A\subseteq G$
as

$\displaystyle A$ $\displaystyle=\bigcup_{i=0}^{C_{2}}A_{i}\cup A^{\prime},$
$\displaystyle A_{0}$ $\displaystyle\sim\mu_{G}\left(\frac{k}{2}\right),$
$\displaystyle A_{i}$ $\displaystyle\sim\mu_{G}(k^{\varepsilon^{2}})\ \ \
(1\leq i\leq C_{2}),$ $\displaystyle A^{\prime}$
$\displaystyle\sim\mu_{G}\left(\frac{k}{2}-C_{2}k^{\varepsilon^{2}}\right).$

From $k\geq(\log n)^{1+\varepsilon}$ we obtain $\frac{k}{2}\geq(\log
n)^{1+\frac{\varepsilon}{2}}$ for large $n$, so up to replacing $\varepsilon$
we can use Lemma 2.6 with $A_{0}$, implying that

$\left|\mathcal{S}_{A_{0}}\left(\omega,C_{1}\log_{k}n\right)\right|\>\geq\>\frac{n}{(k/2)^{2/\varepsilon}}\>\geq\>\frac{n}{k^{2/\varepsilon}}$

holds with high probability (here $C_{1}$ is the constant from Lemma 2.6). At
this point we apply Corollary 2.5 iteratively with each $A_{i}$, with
$k^{\varepsilon^{2}}$ instead of $k$, and $d=(2\varepsilon)^{-1}$, starting at
the first step with $X=\mathcal{S}_{A_{0}}(\omega,C_{1}\log_{k}n)$. If (2.6)
were true for all $1\leq i\leq C_{2}$, then we would have

$|X^{A_{1}\cdot\ldots\cdot
A_{C_{2}}}|\>\geq\>\frac{n}{k^{2/\varepsilon}}\cdot(k^{\varepsilon^{2}})^{C_{2}/2}\>\geq\>nk^{1/\varepsilon}\>>\>n,$

with positive probability, which is impossible. Therefore, (2.6) fails for
some $i\leq C_{2}$. We conclude that

$\displaystyle\left|\mathcal{S}_{A}\left(\omega,(C_{1}+C_{2})\log_{k}n\right)\right|$
$\displaystyle\>\geq\>|X^{A_{1}\cdot\ldots\cdot A_{C_{2}}}|$
$\displaystyle\>\geq\>\frac{n}{(k^{\varepsilon^{2}})^{(\varepsilon^{-1}/2)}}$
$\displaystyle\>=\>\frac{n}{k^{\varepsilon/2}}\>,$

with probability that, up to a multiplicative constant converging to $1$, is
bounded from below by

$\left(1-\frac{2}{(k^{\varepsilon^{2}})^{(2\varepsilon)^{-1}-1}}\right)^{C_{2}k^{\varepsilon^{2}}}\>\geq\>\left(1-\frac{2}{k^{\varepsilon/2}}\right)^{6\varepsilon^{-3}k^{\varepsilon^{2}}}\>\geq\>1-\frac{12\varepsilon^{-3}}{k^{\frac{\varepsilon}{2}-\varepsilon^{2}}}.$

This is going to $1$ as $k$ goes to infinity, and the proof is complete. ∎

######  Remark 2.7.

Our proof of Proposition 2.1 gives $C=O(\varepsilon^{-3})$ for small
$\varepsilon$, but with more work the same argument provides
$O(\varepsilon^{-1-\delta})$ for all fixed $\delta>0$.

##  3\. Bounding the diameter

In this section we study the situation where a set $X\subseteq\Omega$
(typically a sphere), is large. The first observation is that we can reach the
whole $\Omega$ with the help of a few random elements.

######  Lemma 3.1.

Let $G$ be any finite group acting transitively on a set $\Omega$ with
$|\Omega|=n$. Let $X\subseteq\Omega$ with $|X|\geq n/m$ for some $m\geq 1$,
and let $k\geq 4m\log n$. Then, for $B\sim\mu_{G}(k)$, we have $X^{B}=\Omega$
with high probability. More precisely,

$\mathbb{P}_{\mu_{G}(k)}(X^{B}=\Omega)\>\geq\>1-\frac{1}{2^{k/m}}.$

###### Proof.

Let $t$ be the size of a stabilizer, and fix at first any $\omega\in\Omega$.
For each $x\in X$, there are precisely $t$ elements $g\in G$ such that
$x^{g}=\omega$. Thus, for a random $g\in G$, the probability that
$\omega\notin X^{g}$ is

$1-\frac{t|X|}{|G|}\>=\>1-\frac{|X|}{n}\>\leq\>1-\frac{1}{m}.$

For $B\sim\mu_{G}(k)$, we have

$\mathbb{P}_{\mu_{G}(k)}(\omega\notin
X^{B})\>\leq\>\left(1-\frac{1}{m}\right)^{k}\>\leq\>\frac{1}{e^{k/m}}.$

Summing over all $\omega\in\Omega$, we obtain

$\displaystyle\mathbb{P}_{\mu_{G}(k)}(X^{B}=\Omega)$
$\displaystyle\>=\>1-\mathbb{P}_{\mu_{G}(k)}(\omega\notin X^{B}\text{ for at
least one }\omega\in\Omega)$ $\displaystyle\>\geq\>1-\frac{n}{e^{k/m}}.\>$

The proof follows from the lower bound on $k$, because

$n\>\leq\>e^{k/(4m)}\><\>(e/2)^{k/m}.\qed$

One observation should be made at this point. The graphs we are working with
are directed and not vertex-transitive in general, therefore the fact that a
certain sphere with a fixed base point fills $\Omega$, does not immediately
give a bound to the diameter. Looking at (2.1), summing over all
$\omega\in\Omega$ is too expensive. We overcome this problem by applying the
previous argument twice, exploiting the fact that two uniformly random
multisets $A$ and $A^{-1}$ of $G$ have the same distribution as random
variables.

######  Lemma 3.2.

Suppose that, for some $\omega\in\Omega$, for $A\sim\mu_{G}(k)$ we have
$\mathcal{S}_{A}(\omega,t)=\Omega$ with high probability. Then, for
$B\sim\mu_{G}(2k)$, we have

$\mathop{\mathrm{diam}}(\>\mathop{\mathrm{Sch}}(G\circlearrowleft\Omega,B)\>)\>\leq\>2t$

with high probability.

###### Proof.

Let $A_{1},A_{2}\sim\mu_{G}(k)$. From the hypotheses, and the observation
above, we have

$\mathcal{S}_{A_{1}}(\omega,t)\>=\>\mathcal{S}_{A_{2}^{-1}}(\omega,t)\>=\>\Omega$

with high probability. Now let $x,y\in\Omega$. With high probability, there is
$g_{1}\in(A_{1})^{t}$ such that $\omega^{g_{1}}=y$, and also there is
$g_{2}\in(A_{2}^{-1})^{t}$ such that $\omega^{g_{2}}=x$. In particular, there
exists an element $g_{2}^{-1}g_{1}\in(A_{1}\cup A_{2})^{2t}$ such that

$x^{g_{2}^{-1}g_{1}}\>=\>\omega^{g_{1}}\>=\>y.$

This concludes the proof. ∎

Proposition 2.2 now follows easily.

###### Proof of Proposition 2.2.

By an application of Lemma 3.1 with $m=k^{\delta}$, for
$B\sim\mu(k+4k^{\delta}\log n)$, we have $\mathcal{S}_{B}(\omega,t+1)=\Omega$
with high probability. The proof follows from Lemma 3.2. ∎

We are ready to conclude the proof of the main theorem. We observe that, if
$x\in(0,1)$ , then $\frac{1}{1+x}<1-\frac{x}{2}$.

###### Proof of Theorem 1.1.

First, we observe that it is enough to prove the result when
$\varepsilon\in(0,1)$. From $k\geq(\log n)^{1+\varepsilon}$ we obtain
$\frac{k}{4}\geq(\log n)^{1+\frac{\varepsilon}{2}}$ for large $n$, so up to
replacing $\varepsilon$ we can apply Proposition 2.1 with $\frac{k}{4}$
elements. For $A\sim\mu_{G}(k/4)$, $t=O_{\varepsilon}(\log_{k}n)$, we have

$\left|\mathcal{S}_{A}\left(\omega,t\right)\right|\>\geq\>\frac{n}{(k/4)^{\varepsilon/2}}\>\geq\>\frac{n}{k^{\varepsilon/2}}$

with high probability. We now apply Proposition 2.2 with
$\delta=\frac{\varepsilon}{2}$, so that we need
$2(k/4)+8(k/4)^{\varepsilon/2}\log n$ random elements in total. It remains to
check that these are fewer than the $k$ random elements actually available.
Since $k\geq(\log n)^{1+\varepsilon}$, we have

$2(k/4)+8(k/4)^{\varepsilon/2}\log
n\>\leq\>\frac{k}{2}+\frac{k^{\frac{\varepsilon}{2}+\frac{1}{1+\varepsilon}}}{4^{\varepsilon/2}/8}\><\>k$

when $k$ is sufficiently large. The proof is complete. ∎

######  Remark 3.3.

We would like to remark that the $k$ random elements in Theorem 1.1 are not
able to generate the group $G$ in general, as there are transitive permutation
groups of degree $n$ that require up to roughly $n/\sqrt{\log n}$ generators
[11, 12]. In fact, the result in [15] implies that $O(\log n)$ random elements
generate a transitive subgroup with high probability, and Theorem 1.1 shows
that $(\log n)^{1+\varepsilon}$ random elements provide the optimal generation
almost surely.

## Acknowledgements

The first author was funded by a Young Researcher Fellowship from the HUN-REN
Alfréd Rényi Institute of Mathematics, and by the Leibniz Fellowship 2405p
from the Mathematisches Forschungsinstitut Oberwolfach (MFO). The second
author was supported by the Royal Society.

## References

  * [1] N. Alon, A. Barak, U. Manber, On disseminating information reliably without broadcasting, in Proc. Seventh Internat. Conf. on Distributed Computing Systems (ICDS) (1987), 74-81.
  * [2] N. Alon, Y. Roichman, Random Cayley graphs and expanders, Random Structures and Algorithms 5(2) (1994), 271-284.
  * [3] L. Babai, On the diameter of Eulerian orientations of graphs, in Proc. 17th Ann. Symp. on Discr. Alg. (SODA) (2006), 822-831.
  * [4] B. Bollobás, W. Fernandez De La Vega, The diameter of random regular graphs, Combinatorica 2(2) (1982), 125-134.
  * [5] E. Breuillard, B. Green, B. Guralnick, T. Tao, Expansion in finite simple groups of Lie type, Journal of the European Mathematical Society 17 (2015), 1367-1434.
  * [6] C. Dou, M. Hildebrand, Enumeration and random random walks on finite groups, Annals of Probability 24(2) (1996), 987-1000.
  * [7] S. Eberhard, U. Jezernik, Babai’s conjecture for high-rank classical groups with random generators, Inventiones Mathematicae 227 (2022), 149-210.
  * [8] J. Friedman, A. Joux, Y. Roichman, J. Stern, J.P. Tillich, The action of a few permutations on $r$-tuples is quickly transitive, Random Structures and Algorithms 12(4) (1998), 335-350.
  * [9] J.L. Gross, Every connected regular graph of even degree is a Schreier coset graph, Journal of Combinatorial Theory (B) 22(3) (1977), 227-232.
  * [10] H.A. Helfgott, Growth in groups: ideas and perspectives, Bulletin of the American Mathematical Society 52(3) (2015), 357-413.
  * [11] L.G. Kovács, M.F. Newman, Generating transitive permutation groups, Quarterly Journal of Mathematics 39 (1988), 361-372.
  * [12] A. Lucchini, F. Menegazzo, M. Morigi, Asymptotic results for transitive permutation groups, Bulletin of the London Mathematical Society 32(2) (2000), 191-195.
  * [13] B. Murphy, Group action combinatorics, https://arxiv.org/pdf/1907.13569 (2019).
  * [14] Y. Roichman, On random random walks, Annals of Probability 24(2) (1996), 1001-1011.
  * [15] L. Sabatini, Random Schreier graphs and expanders, Journal of Algebraic Combinatorics 56(3) (2022), 889-901.
  * [16] S.V. Skresanov, On directed and undirected diameters of vertex-transitive graphs, https://arxiv.org/pdf/2312.12943 (2023).