2

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!!

tehjh
  • 384
  • Currently, my friends and I have constructed plausible minimal configurations for small values of n up to n=17, but there is no clear pattern so far. – tehjh Oct 18 '13 at 14:26

1 Answers1

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$

Ross Millikan
  • 374,822
  • It's easy to show that the maximum is $\lfloor \frac{n}{2} \rfloor \times \lceil \frac{n}{2} \rceil $. Any such $a \times b$ rectangle must satisfy $a+b \geq n$, hence that is the maximal area. – Calvin Lin Oct 15 '13 at 20:49
  • Correct me if I'm wrong but the construction doesn't seem to work when k and n are not coprime. – tehjh Oct 18 '13 at 13:45
  • @tehjh: You are correct, although it can be patched up a bit. I don't think it will expand the minimal rectangle much, but haven't worked on it. As OP was asking about asymptotics, we can just ask that $k$ be prime and be assured it works for those. – Ross Millikan Oct 18 '13 at 14:26
  • By considering the square in to top row, and square in the adjacent column, I also got a lower bound of about $n$. I actually wonder what the limit points of the sequence $f(n)/n$ are where $f(n)$ is the minimum for a given $n$. – tehjh Oct 18 '13 at 17:01
  • Sorry this is way overdue but looking at this again the bound this construction produces seems to be more like $O(n^{3/2})$ because of the rectangles produced by the corner with the "slope" of the first $k$ rows – tehjh Mar 05 '17 at 14:46