Longest increasing subsequence on pairs Given a sequence of pairs $(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)$ such that $a_1 \le a_2 \le ... \le a_n$ (i.e, sorted in ascending order by $a$'s), we solve the longest increasing subsequence problem for $b$'s. Now suppose the length of the longest increasing subsequence is $X$.

If we now sort the initial sequence by the second component and solve the LIS problem for $a$'s, is the length of this sequence also equal to $X$?

Intuitively I think this is true, but I don't know if it really is.
When you solve the longest increasing subsequence problem in its original formulation, you are finding the longest sequence $i_1,\ldots,i_\ell$ such that
$$
a_{i_1} &lt; \cdots &lt; a_{i_\ell} \\
b_{i_1} &lt; \cdots &lt; b_{i_\ell}
$$
This holds even if you shuffle the indices. Since the object you are maximizing is symmetric in the $a$s and $b$s, you will get the same length in both cases.