On diameters of the Cayley graphs of the symmetric groups

A. Kuznetsov,   An. Shlyopkin

Let \(S_n\) be the symmetric group of degree \(n\), let \(x_1=(1, 2)\), \(x_2=(2, 3)\), …, \(x_{n-1}=(n-1, n)\), \(x_n=(1, n)\) be generators of \(S_n\), and let \(X=\{x_1,x_2,\ldots,x_n\}\).

We proved the following

Theorem. The diameter of the Cayley graph of \(S_n\) relative to \(X\) is equal to
\(\ \ (i)\ \ \ \) \(\dfrac{n^2}{4}\) for even \(n=2k\) and corresponds to only one permutation \[\begin{pmatrix}1&2&\dots&k-1&k&k+1&k+2&\dots&2k-1&2k\\k+1&k+2&\dots&2k-1&2k&1&2&\dots&k-1&k\end{pmatrix};\] \(\ \ (ii)\ \ \) \(\dfrac{n^2-1}{4}\) for odd \(n=2k+1\) and corresponds to only two permutations \[\begin{pmatrix}1&2&\dots&k&k+1&k+2&k+3&\dots&2k&2k+1\\k+1&k+2&\dots&2k&2k+1&1&2&\dots&k-1&k\end{pmatrix},\] \[\begin{pmatrix}1&2&\dots&k-1&k&k+1&k+2&\dots&2k&2k+1\\k+2&k+3&\dots&2k&2k+1&1&2&\dots&k&k+1\end{pmatrix}.\]