Given $n$ coloured squares in an $n$ by $n$ square board of unit squares, one in each row and column (which we will call a permutation), let the minimum area (over all permutations) of the largest rectangle that can be drawn with sides parallel to the edges of the big square without touching a coloured square be $f(n)$. Does there exist real $c$ such that $f(n)<cn$ for all sufficiently large $n$?
It would seem easier to start with the continuous version, with $n$ points in a unit square and the anologous bound of $c/n$.
Context: This was an old question that I asked:
Maximal rectangle in a permutation
where I was attempting to find bounds on the size of the largest rectangle that could be found in a permutation ($n$ squares each in a different row and column) in an $n\times n$ square board. Recently a friend of mine proved an upper bound of the form $O(n\log n)$ via a greedy algorithm on the related question of finding the largest rectangle parallel to the sides not touching any of $n$ points placed in a unit square. The question of a lower bound that is better than linear, however, still seems rather difficult.
