I was reading about Relations and Partial Orders and it states:
Corollary 7.9.4. Every partially ordered set with $n$ elements has a chain of size greater than $\sqrt n$ or an antichain of size at least $\sqrt n$.
I know the reasoning behind this, however I was not able to understand the text following this:
As an application, consider a permutation of the numbers from $1$ to $n$ arranged as a sequence from left to right on a line. Corollary 7.9.4 can be used to show that there must be a $\sqrt n$ length subsequence of these numbers that is completely increasing or completely decreasing as you move from left to right. For example, the sequence $7, 8, 9, 4, 5, 6, 1, 2, 3$ has an increasing subsequence of length 3 (for example, 7, 8, 9) and a decreasing subsequence of length 3 (for example, 9, 6, 3). The proof of this result is left as an exercise that will test your ability to find the right partial order on the numbers in the sequence.
I don't understand how Corollary 7.9.4. can be used to show that there must be a $\sqrt n$ length subsequence of these numbers that is completely increasing or completely decreasing as you move from left to right.
And how is this permutation of numbers from $1$ to $n$ relatable to POSETs? POSET consists of a set and a partial order(a relationship of a special kind). So do we consider the numbers in the sequence as the elements of the set? And when they say that "proof of this result is left as an exercise that will test your ability to find the right partial order on the numbers in the sequence", do they mean the example sequence which they mentioned above or any permutation sequence in general?
And one last thing, the example sequence they gave: $7, 8, 9, 4, 5, 6, 1, 2, 3$, will this be considered as topological sort for a particular POSET?
PS:
An antichain in a poset is a set of elements such that any two elements in the set are incomparable.
Given a permutation $\sigma$ on the set $S_n=\{1,2,\ldots,n\}$ define the following order relation on $S_n$: $$x \lesssim y \quad\text{ iff }\quad x \leq y \quad\text{and}\quad \sigma^{-1}(x) \leq \sigma^{-1}(y).$$ So you'll have $x \lesssim y$ whenever $x \leq y$ and $x$ appears first in the sequence of images of $\sigma$, when going from left to right.
Hence, you have a chain $a_1 \lesssim \cdots \lesssim a_k$ if $a_1, \ldots, a_k$ is a increasing sub-sequence of $\sigma(1), \ldots, \sigma(n)$.
And you'll have an anti-chain $b_1, \ldots, b_m$ if $b_1 \leq \cdots \leq b_m$ but $\sigma^{-1}(b_1) \geq \cdots \geq \sigma^{-1}(b_m)$. By the corollary you mention, the poset has at least one $\sqrt{n}$-elements chain or anti-chain, and therefore, the sequence $(\sigma(1), \ldots, \sigma(n))$ has at least one $\sqrt{n}$-elements increasing sub-sequence or a $\sqrt{n}$-elements decreasing one.
In the example you refer to, the result is a poset consisting of the union of three three-element chains: $$1 \lesssim 2 \lesssim 3, \quad 4 \lesssim 5\lesssim 6, \quad\text{and}\quad 7 \lesssim 8 \lesssim 9.$$ It is immediate that, indeed, $1,2,3$, and $4,5,6$ and $7,8,9$ are increasing sequences (and they are sub-sequences of $(7,8,9,4,5,6,1,2,3)$).
On the other hand, if you pick one element from each sequence, from the third to the first, it forms a decreasing sub-sequence of $(7,8,9,4,5,6,1,2,3)$.
If you play around a little bit with different permutations (even with $n \leq 9$), you'll see that the poset can be much less trivial than this one.
But the real point is that one can derive the conclusion for the general case using the result about posets.