2 added 84 characters in body

These runs are strongly related to Young tableaux. So it is the best to first make a tableau that has the corresponding property. This we can construct by induction: Start with 1, then make a copy of it +1 and put it below, then copy it +2 and put it right from it. So you should get: $\begin{array}{cc} 1&3\cr 2&4\cr \end{array}$. After repeating it on, we get $\begin{array}{cccc} 1&3&9&11\cr 2&4&10&12\cr 5&7&13&15\cr 6&8&14&16\cr \end{array}$ and so on.

To make a sequence of this, first take the last row of the tableau, then the last but one and so on, so you should get $6, 8, 14, 16, 5, 7, 13, 15, 2, 4, 10, 12, 1, 3, 9, 11$. Now, without giving a formal proof, any long enough run must skip over two correspondingly big "breaks" in the matrix which will make it have a large width. Unless I am mistaken, a run of length $c\sqrt n$ should have width $\Omega(c n)$.

Update: I was mistaken, as pointed out by Aaron, so the width should be smaller.

1

These runs are strongly related to Young tableaux. So it is the best to first make a tableau that has the corresponding property. This we can construct by induction: Start with 1, then make a copy of it +1 and put it below, then copy it +2 and put it right from it. So you should get: $\begin{array}{cc} 1&3\cr 2&4\cr \end{array}$. After repeating it on, we get $\begin{array}{cccc} 1&3&9&11\cr 2&4&10&12\cr 5&7&13&15\cr 6&8&14&16\cr \end{array}$ and so on.

To make a sequence of this, first take the last row of the tableau, then the last but one and so on, so you should get $6, 8, 14, 16, 5, 7, 13, 15, 2, 4, 10, 12, 1, 3, 9, 11$. Now, without giving a formal proof, any long enough run must skip over two correspondingly big "breaks" in the matrix which will make it have a large width. Unless I am mistaken, a run of length $c\sqrt n$ should have width $\Omega(c n)$.