If found this problem in the book "The probabilist method" of Alon and Spencer:
Prove that there is an absolut constant $c>0$ with the following property: let $A$ be a $n\times n$ matrix with pairwise distinct entries. Then there is a permutation of the rows of $A$ so that no column in the permuted matrix contains an increasing subsequence of lenght at least $c\sqrt{n}$.
I have no idea of how to begin.
I spent some time going through all the exercises of this book two years ago and here is the solution I found for this one.
We let $c$ be undetermined for the moment. Given a sequence of $n$ distinct numbers, we say that it is good if it has no increasing subsequence of length at least $l = \lceil{c\sqrt{n}}\rceil$, otherwise we call it bad. Suppose we have a random permutation $\pi$ of $[n]$. Now, if we fix some indices $1\leq i_1 < i_2< \ldots < i_{l}\leq n$, the chance that $\pi(i_1), \pi(i_2),\ldots, \pi(i_{l})$ is increasing is \begin{align} \mathbb{P} \left[ \pi(i_1),\ldots, \pi(i_{l}) \text{ is bad}\right] = \frac{1}{l!}. \end{align} Therefore, the chance that $\pi(1),\ldots,\pi(n)$ is bad is bounded by \begin{align} \mathbb{P}(\pi(1),\ldots, \pi(n) \text{ is bad}) &\leq \bigvee\limits_{1\leq i_1 < \ldots < i_{l} \leq n}{\mathbb{P} [ \pi(i_1),\ldots, \pi(i_{l}) \text{ is bad}} ]\\ &= \binom{n}{l}\frac{1}{l!}, \end{align} Now, given an $n\times n$ matrix of distinct numbers, the chance that a random permutation of the rows creates at least one bad column satisfies \begin{equation} \mathbb{P} (\exists \text{ bad column}) \leq n \binom{n}{l} \frac{1}{l!}. \end{equation} Now, we have some freedom in choosing $c$, so let $c>e$, implying that \begin{equation} e < \frac{\lceil{ c\sqrt{n}} \rceil}{\sqrt{n}} = \frac{l}{\sqrt{n}},\qquad \implies\qquad \frac{e}{l} < \frac{1}{\sqrt{n}}. \end{equation} Then we can use the bound $\binom{n}{l} \leq ((ne)/l )^l$ to obtain \begin{align} \mathbb{P} (\exists \text{ bad column})\leq n \binom{n}{l} \frac{1}{l!}< n \left( \frac{n\cdot e}{l} \right)^{l}\frac{1}{l!}< n \frac{n^{\frac{l}{2}}}{l!} \end{align} We use Stirling's approximation in the form $l! \geq \sqrt{2\pi l }\cdot l^{l}e^{-l} $ to get the bound \begin{equation} \mathbb{P} (\exists\text{ bad column})\leq n \frac{n^{\frac{l}{2}}e^l}{\sqrt{2\pi l}l^{l} } <\frac{n\cdot n^{-\frac{l}{2}}}{\sqrt{2\pi l}} = \frac{n^{1 - \lceil{c\sqrt{n}\rceil}/2}}{\sqrt{2\pi \lceil{c\sqrt{n}\rceil}}}. \end{equation} Our choice of $c>e$ implies that $l = l(n) \geq 3$ for all $n\geq 1$, and the above bound becomes \begin{equation} \mathbb{P} (\exists\text{ bad column})< \frac{ n^{-\frac{1}{2}}}{\sqrt{6\pi}} < \frac{1}{\sqrt{6 \pi}}. \end{equation} So, with positive probability, there are no bad columns, and so a permutation having no bad columns exists. Moreover, the above probability that a random permutation produces a bad column decreases at least as fast as $n^{1- e\sqrt{n}/2}$, so if we want to obtain an instance of such a permutation, a random one will very likely do the trick!