Largest subsequence in a random ordering Suppose I have the set $[n]$ and I arrange this uniformly at random into a sequence, which I can represent as a map $\pi_n:[n]\to [n]$. Now I want to find, on expectation, the largest possible subsequence in $\pi$ (not necessarily consecutive) that is increasing.
In other words, given a $\pi_n$, there exists a maximum value of $m\leq n$ such that there exists $x_1,x_2,...,x_m\in[n]$ which are increasing and $\pi_n(x_1),\pi_n(x_2),...,\pi_n(x_m)$ is also increasing. I want to find the expected value of this $m$ where the expectation is over the uniform distribution of $\pi_n$ 's.
Also, I arrived at this problem while studying an algorithmic problem. So I am not too keen on the exact expression, a constant approximation would suffice - but an exact expression would be just as good. What I mean is that I would be happy if I could know if this is of the order of $n$ or maybe of the order of $\sqrt{n}$ or maybe of the order of $\log n$.

This is known as 'Ulam's problem'. The expectation of the longest increasing subsequence in a random permutation is of order $2\sqrt{n}$. See this paper (and references) for more information https://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00307-0/S0894-0347-99-00307-0.pdf
