Consider a partition $f:S_n\rightarrow [n]$ of $S_n$ into $n$ parts. Denote the permutations that map $j$ to $k$ by $s(j,k)$. Set $S(f):=\Sigma_{1\leq i,j\leq n}max_{1\leq k\leq n}|f^{-1}(i)\cap s(j,k)|$. I would like to choose a partition $f$ so that it maximizes $S(f)$.
My intuition says that the maximum $S(f)$ is $2n!$ and that it is only achieved by partitioning the permutations of $S_n$ either according to where they map $c$, or according to what they map to $c$, where $c$ can be any specific element of $[n]$. In fact, it appears that this technique naturally extends to partitions of $S_n$ into any number of parts. However, I do not have a proof that this is indeed so.
The above problem seems very natural to me. Though I only thought it up very recently, it would not surprise me if it was a known problem and there were some results about it, or even a complete solution. So, if anyone could point to a paper with some work or a solution of this problem, I would be grateful.
Edit: I have shown that my intuition was wrong for a factor of about $\frac{logn}{logloglogn}$.
