4
$\begingroup$

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)}$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Yes, I am aware of, say, dl.acm.org/citation.cfm?id=2717 $\endgroup$
    – H A Helfgott
    Mar 8, 2019 at 19:12
  • 1
    $\begingroup$ It was proved in a 1991 paper by Liebeck and Saxl (using CFSG) that, in a finite $2$-transitive group not equal to $A_n$ or $S_n$, all non-identity elements move at least $n/3$ points, so I think your hypotheses imply that $\langle S \rangle = A_n$ or $S_n$. $\endgroup$
    – Derek Holt
    Mar 8, 2019 at 20:13
  • 1
    $\begingroup$ $O(n)$ estimate holds if there exists an element $a$ which belongs to $O(n)$ supports of permutations from $S$: using $O(n)$ steps we may make $i=a$, after that using $O(n)$ steps making $j$ belong to support of some permutation containing $a$. Is it possible that $S$ does not have a subset $S'$ which also generates a 2-transitive subgroup but satisfies this property? $\endgroup$
    – Fedor Petrov
    Mar 8, 2019 at 20:36
  • 1
    $\begingroup$ (continuation) well, we have $S'\subset S$ which generates the same subgroup as $S$ and $|S'|=O(n\log n)$ (enumerate the elements of $S$ and take them one by one, when the size of generated subgroup increases it is multiplied at least by 2). This gives $O(n\log n)$ estimate in the original question, yes? $\endgroup$
    – Fedor Petrov
    Mar 8, 2019 at 20:45

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Yes, it is less or more what I mean (except Babai's result which I did not know). The last step may be explained also as follows: if the diameter of a graph equals $D$, if contains $D/m$ vertices with pairwise distances at least $m$ (on the longest path), thus it can not be covered by less than $D/m$ balls of radius less than $m/2$. $\endgroup$
    – Fedor Petrov
    Mar 8, 2019 at 22:53
  • $\begingroup$ Yes, that's nicer. $\endgroup$
    – H A Helfgott
    Mar 8, 2019 at 23:57
  • $\begingroup$ and in the second part, I possibly had slightly different argument: for any element $j\ne 1$ consider the shortest path from $j$ to 1 in the Schreier graph on $\{1,\dots,n\}$. It corresponds to at most $n-1$ permutations $\sigma_1,\dots,\sigma_k\in S$ such that $\sigma_k\sigma_{k-1}\ldots\sigma_1 j=1$. Choose minimal $i$ for which the support of $\sigma_i$ contains 1 (such $i$ exists, otherwise $(\prod \sigma_i)j=(\prod \sigma_i)1$), the product $\sigma_{i-1}\ldots \sigma_1$ maps $j$ to some element lying in the support of $\sigma_i$, which contains also 1. $\endgroup$
    – Fedor Petrov
    Mar 9, 2019 at 6:49
  • $\begingroup$ (continuation) This uses at most $2n-2$ permutations on two first steps, $O(n)$ is used only when we say that 1 is contained in $O(n)$ supports which in total contain $O(n)$ elements. $\endgroup$
    – Fedor Petrov
    Mar 9, 2019 at 6:52
  • 2
    $\begingroup$ As I pointed out in an earlier comment, your hypotheses imply that $\langle S \rangle = A_n$ or $S_n$ (provided that $n$ is large enough compared with bound on the support) so, in your final remark, the group certainly is $k$-transitive for $k \le n-2$. $\endgroup$
    – Derek Holt
    Mar 9, 2019 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.