A problem of permutations using the probabilistic method. 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.
 A: 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!
