Timeline for Diameter for permutations of bounded support
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9, 2019 at 12:20 | comment | added | Derek Holt | 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$. | |
| Mar 9, 2019 at 6:52 | comment | added | Fedor Petrov | (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. | |
| Mar 9, 2019 at 6:49 | comment | added | Fedor Petrov | 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. | |
| Mar 8, 2019 at 23:57 | comment | added | H A Helfgott | Yes, that's nicer. | |
| Mar 8, 2019 at 22:53 | comment | added | Fedor Petrov | 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$. | |
| Mar 8, 2019 at 22:26 | history | answered | H A Helfgott | CC BY-SA 4.0 |