Let $G=S_{n^2}$ the symmetric group on a grid of $n^2$ letters.
Now $G$ contains a maximal subgroup $H \cong S_n \wr S_n$ by the O'Nan-Scott theorem, and we can think of elements that look something like $(\sigma_1,\dots,\sigma_n)\tau$ where $\sigma_i$ acts on the $i$th row of letters, permuting letters within the row, and $\tau$ permutes the rows themselves.
Similarly, there exists another isomorphic copy of this subgroup, call it $H'$ that acts as above but on columns. By maximality, $G=\langle H, H' \rangle$.
So then my question: what is the diameter of the Cayley graph $\Gamma (G,H\cup H')$?
Best Answer
OK here is an answer, showing the diamater is $3$ for almost all $n$.
The diameter cannot be $2$, simply by size considerations of $|HH'|$, which has relative size in $S_{n^2}$ at most (by Stirling's approximation) \begin{equation} \frac{(n!)^{2n+2}}{(n^2)!}\sim \sqrt{2\pi}\Big(\frac{2\pi}{e^2}\Big)^n\Big(\frac{n^3}{e^n}\Big)^n \rightarrow 0 \end{equation}
Now to show it has diameter $3$, we need to be able to transform any permutation in $S_{n^2}$ to the identity via an element of $H'HH'$. Write this arbitrary permutation as an $n\times n$ matrix, for example \begin{equation} \begin{pmatrix} 4&3&9\\\color{red}{1}&2&7\\5&6&8 \end{pmatrix} \end{equation} Since $1$ is in the fourth position (left to right, top to bottom), this says that the permutation sends $4$ to $1$. [Work the examples from bottom to top to see this matrix transformed to the identity.]
In order for an element of $H'$ to send a matrix to the identity, a necessary and sufficient condition is that in each column, all entries are equivalent $\pmod{n}$. Call such a matrix mod-constant. To get this to the identity, first sort the columns by this common modulus, then sort within each column. Example: \begin{equation} \begin{pmatrix} 6&4&8\\3&7&5\\9&1&2 \end{pmatrix} \rightarrow \begin{pmatrix} 4&8&6\\7&5&3\\1&2&9 \end{pmatrix} \rightarrow \begin{pmatrix} 1&2&3\\4&5&6\\7&8&9 \end{pmatrix} \end{equation}
In order to get an arbitrary matrix to be mod-constant via an element of $H$, it is necessary and suficient that each row of the matrix has no two elements of the same remainder $\pmod{n}$. Call such a matrix good. To get it into the mod-constant state, just sort each row by remainder. Example: \begin{equation} \begin{pmatrix} 4&6&8\\5&3&7\\1&2&9 \end{pmatrix} \rightarrow \begin{pmatrix} 6&4&8\\3&7&5\\9&1&2 \end{pmatrix} \end{equation}
Finally, in order to get an arbitrary matrix into a good configuration via an element of $H'$, it is necessary to permute each column such that no two elements of the same remainder end up in the same row. To show this is possible, we reduce every entry in our matrix $\pmod{n}$. Then we have an $n\times n$ grid, with $n$ 0's, $n$ 1's, etc.
Define for each $0\le i<n$ the set $A_i$ to be the column indices containing at least one $i$. Then the family $\{A_i\}$ satisifes the conditions of Hall's marriage theorem, and so there is a transversal; that is, a set of column indices $\{c_0,c_1,\ldots,c_{n-1}\}$ that are mutually distinct and column $c_i$ contains $i$. Now permute each column to bring that $i$ to the top row. The first row is now good, and we are left with an $(n-1)\times n$ grid with $(n-1)$ 0's, $(n-1)$ 1's, etc. So we repeat this process, leaving the first row alone. Inductively we make this arbitrary matrix good, and our proof is complete. Example: \begin{equation} \begin{pmatrix} \color{red}{4}&3&9\\1&2&7\\5&\color{red}{6}&\color{red}{8} \end{pmatrix}\rightarrow \begin{pmatrix} 4&6&8\\1&2&\color{blue}{7}\\\color{blue}{5}&\color{blue}{3}&9\end{pmatrix} \rightarrow \begin{pmatrix} 4&6&8\\5&3&7\\1&2&9 \end{pmatrix} \end{equation}