I am working on an exercise mentioned in passing on page 4 immediately under section 1.2 of the following notes, and would like a hint as to how to proceed (please do not provide a solution): https://math.mit.edu/~rstan/papers/perms.pdf#:~:text=We%20write%20permutations%20w%20Sn%20as%20words%2C%20i.e.%2C,%3C%20%3C%20aik%2C%20and%20similarly%20for%20decreasing%20subsequence.
Relevant Problem Info:
Given a permutation $\omega$ we define $is(\omega)$ to be the length of the longest increasing subsequence of $\omega$, and $ds(\omega)$ the length of the longest decreasing subsequence of $\omega$. For example, the permutation $\omega = 1243$ in $S_4$ has $is(\omega) = 3, ds(\omega) = 2$ because of the subsequences $124$ and $43$. The claim is that using the Erdos-Szekeres theorem (stated below) we can easily deduce that for sufficiently large $n$:
$$\mathbb{E}(n) = \frac{1}{n!}\sum_{\omega \in S_n}is(\omega) \geq \sqrt{n}$$
In other words, the expected value of the length of the longest increasing sequence in a permutation is greater than $\sqrt{n}$.
The Erdos-Szekeres theorem is stated earlier in the notes as:
Let $p, q \geq 1$. If $\omega \in S_{pq+1}$, then we must have either $is(\omega) > p$ or $ds(\omega) > q$.
My thoughts so far:
For any arbitrary $n > 1$ we can write $n = (n-1)\cdot 1 + 1$ which tells us that for any element of $S_n$ either $is(\omega) > 1$ or $ds(\omega) > n-1$. We know there is only a single permutation with $ds(\omega) > n-1$ (and so therefore equal to $n$) which is just $n, n-1, n-2, …, 1$ where this has $is(\omega) = 1$. Hence all other permutations have $is(\omega) \geq 2$. The problem with this application of the theorem doesn't really seem to tell us something that we don't already know, but I'm also unsure of a useful representation of $n$ in terms of factors $p, q$ which would work for arbitrary $n$.
I feel as though there is potentially some use of Stirling's approximation $\binom{2n}{n} \sim \frac{2^{2n}}{\sqrt{n\pi}}$ otherwise I am unsure how the $\sqrt{n}$ appears in the expression.
Any help in the right direction would be greatly appreciated.
Best Answer
Let $p,q \geq 1$. If $\omega \in S_{pq+1}$, then $\text{is}(\omega) > p$ or $\text{ds}(\omega) > q$. This means that $\text{is}(\omega)\text{ds}(\omega) > pq$, therefore, $\text{is}(\omega)\text{ds}(\omega) \geq pq + 1 = n$. We note that $$\textbf{E}(n) = \frac{1}{n!}\sum_{\omega \in S_{n}}\text{is}(\omega) = \frac{1}{n!}\sum_{\omega \in S_{n}}\text{ds}(\omega)$$ by symmetry. Then, by AM-GM, $$2\textbf{E}(n) = \frac{1}{n!}\sum_{\omega\in S_{n}}(\text{is}(\omega) + \text{ds}(\omega)) \geq \frac{2}{n!}\sum_{\omega\in S_{n}}\sqrt{\text{is}(\omega)\text{ds}(\omega)} \geq \frac{2}{n!}\sum_{\omega\in S_{n}}\sqrt{n} = 2\sqrt{n}$$ It follows that $\textbf{E}(n) \geq \sqrt{n}$.