I am struggling to understand the following example taken from Seidenberg's paper (1959).
"A well-known example of a sequence of $mn$ terms like the following: $$m,m-1,\ldots,1,2m,2m-1,\ldots,m+1,3m,3m-1,\ldots,2m+1,\ldots,nm,nm-1,\ldots,(n-1)m+1$$ shows that the bound given by Erdős-Szekeres theorem is exact."
Specifically, how do we construct the sequence like that, and also what's the reason this sequence shows that the bound is exact or tight.
Moreover, if we assume that $m=n$, can we write $$n,n-1,\ldots,1,2n,2n-1,\ldots,n+1,3n,3n-1,\ldots,2n+1,\ldots,n^2,n^2-1,\ldots,(n-1)n+1$$
I would really appreciate if you have any suggestions/hints.
Thank you.
Break the sequence into $n$ blocks:
$$\begin{align*} &m,m-1,m-2,\ldots,1\\ &2m,2m-1,2m-2,\ldots,m+1\\ &3m,3m-1,3m-2,\ldots,2m+1\\ &\qquad\qquad\qquad\quad\vdots\\ &nm,nm-1,nm-2,\ldots,(n-1)m+1 \end{align*}$$
Call these blocks $B_1,B_2,B_3,\ldots,B_n$, so that $B_k$ starts with $km$. Each block is a descending sequence of $m$ terms, and if $1\le k<\ell\le n$, every term in $B_k$ is less than every term in $B_\ell$. That is, each term in each block is bigger than every term in the earlier blocks.
Suppose that you have a subsequence with more than $m$ terms. Then it’s too big to fit in one block, so it must have terms in two different blocks, say $B_k$ and $B_\ell$, where $k<\ell$. But then it’s not a decreasing sequence: the term in $B_\ell$ comes later than the term in $B_k$ but is larger. Thus, the sequence has no decreasing subsequence of length $m+1$.
Now suppose that you have a subsequence with more than $n$ terms. There are only $n$ blocks, so some block, must contain two terms. The earlier term in that block is larger than the later term in that block, so the subsequence cannot be increasing. Thus, the sequence has no increasing subsequence of length $n+1$.
This shows that it’s possible to have a sequence of $mn$ real numbers that has neither a decreasing subsequence of length $m+1$ nor an increasing subsequence of length $n+1$. The Erdős-Szerkeres theorem, on the other hand, says that any sequence of $mn+1$ or more real numbers does have either a decreasing subsequence of length $m+1$ or an increasing subsequence of length $n+1$. The example shows that the length requirement of $mn+1$ cannot be reduced to a length requirement of just $mn$: at that length we have a counterexample.
You may find this pictorial example of the case $m=n=4$ helpful.
Yes, if $m=n$ the counterexample here takes the form that you wrote at the end of the question.