Diameter for permutations of bounded support Let $S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $\sigma\in S$ moves $O(1)$ elements of $\{1,2,\dotsc,n\}$. Let $\Gamma$ be the graph whose set of vertices is the set of ordered pairs $(i,j)$, $1\leq i,j\leq n$, $i\ne j$, and whose edges are $((i,j), (i,j)^\sigma)$, $\sigma\in S$. (In other words, $\Gamma$ is a Schreier graph.) Assume $\Gamma$ is connected, i.e., $S$ generates a $2$-transitive group.
Must it be the case that $\textrm{diam}(\Gamma) = O(n)$? Could it be the case that $\textrm{diam}(\Gamma)\gg n^{1+\delta}$, $\delta>0$, or even $\delta=1$?
What are the answers to these questions if we assume that $\langle S\rangle$ is all of $\textrm{Alt}(n)$ or $\textrm{Sym(n)}$?
 A: The following is an answer that is also an attempt at interpreting Fedor Petrov's remark above. He may have had a somewhat different solution in mind, but the following procedure should be valid regardless. The diameter turns out to be $O(n)$.
First of all: Babai proved that a subgroup chain in $\textrm{Sym}(n)$ is of size $O(n)$ (https://www.tandfonline.com/doi/pdf/10.1080/00927878608823393) and so we can assume that $|S|=O(n)$.
Since $|S|=O(n)$ and each element of $S$ has bounded support, an average element of $\Sigma=\{1,2,\dotsc,n\}$ is contained in the support of $O(1)$ elements of $S$. Take an element that is not above average; call it $1$.
Every element of $\Sigma$ can be taken to $1$ in $O(n)$ steps. All but $O(1)$ elements of $S$ fix $1$. They generate a subgroup of $\text{Sym}(n-1)$ with a certain number of orbits. All that each of the elements of $S$ not fixing $1$ can do is join $O(1)$ of those orbits. Denote the set of all such elements by $S_0$. Since $\Gamma$ is connected, we see that there were $O(1)$ orbits to start with (otherwise they could not be joined by the $O(1)$ elements of $S_0$).
Hence, there is a set of $c=O(1)$ vertices in $\Gamma$ (all, incidentally, of the form $(1,i)$) with the property that every vertex in $\Gamma$ is at distance $\leq C n$ ($C$ a constant) of at least one of them. If any two such balls of radius $C n$ intersect, we join them (and now we have a ball of radius $2 C n$. We proceed until we have a partition of the set of vertices into $c'=O(1)$ sets. Since $\Gamma$ is connected, there has to be an edge between at least two of the sets of the partition. We join those sets, and proceed in this fashion until we have joined all sets. In the end, we obtain that the diameter of $\Gamma$ is $\leq C c n + c = O(n)$.
I'm in Boris Bukh's office today (he whose avatar here is "Boris Bukh"). He points out that, iterating this argument, we obtain a bound of $O_k(n)$ for the diameter of the Schreier graph $\Gamma_k$ of ordered $k$-tuples induced by a set $S$ of permutations of bounded support, assuming that $\langle S\rangle$ is $k$-transitive.
