Maximal rectangle in a permutation

Question

Suppose you have a permutation of n elements, and it is represented by colouring squares in a n by n grid of squares, where only one square is coloured in each row or column. Find the minimum area of the largest rectangle in the grid that does not contain any coloured square taken over all permutations of n elements in terms of n, if possible. (If not, asymptotics are fine). Edit: This is just a little problem I came up with that seems to be quite hard. Any help would be greatly appreciated!!

Answer 1

Not a solution, but an asymptotic upper bound. Let $k=\lfloor \sqrt n\rfloor$ (it works best with $n$ coprime to $k$). Now take the permutation $i \to ik \pmod n$ There are rectangles $(k-1)\times (2k)$ with area about $2n$ all over the place. Maybe somebody can do better or prove this optimal. In the other direction, the identity permutation has squares with side $\frac 12(n-1)$ so area about $\frac {n^2}4$ Hope this helps.

Added: we can show that there is a rectangle of size $n-1$. Decompose the square into one $n \times 1$ rectangle along one edge and $n$ rectangles $(n-1) \times 1$ in the other direction. Only $n$ of thexe can have a coloured square in them. This means asymptotically we are somewhere between $n$ and $2n$