Definitions
- $X=\{(1,i_1),(2,i_2),...,(n,i_n)\}$. Here $i_1,i_2,...,i_n$ is permutation $\sigma $ of $\{1,2,...,n\}.$
- $R$ is a relation defined as follows $$(k,i_k)R(l,i_l)\iff k\leq l\text{ and }i_k\leq i_l.$$
- The dimension of the poset $(X,R)$ is the smallest number of linear extensions whose intersection is $(X,R)$.
Problem: Prove that the dimension of the partial order set $(X,R)$ is $2$, provided that $i_1,i_2,..,i_n$ is not the identity permutation $1,2,...,n$.
My Attempt: It is easy to see that the dimension of $(X,R)$ is $1$ when $\sigma=1,2,3,...,n$. Now suppose that $\sigma\neq 1,2,3,...,n.$ Then we have to show that the dimension of $(X,R)$ is $2$. I am guessing that a constructive proof is required for this problem where we need to construct two different sets of linear extensions, but this seems very difficult. So if you are aware of alternative approaches then any hints or suggestions would be much appreciated.
Here is the original problem text from Introductory Combinatorics by Richard A. Brualdi.
Standard lexicographic order, $L_1$, and colexicographic order, $L_2$, defined by $$ \begin{aligned} (a,b)L_1(c,d)&\Longleftrightarrow a<c\text{ or } (a=c\text{ and }b\le d),\\ (a,b)L_2(c,d)&\Longleftrightarrow b<d\text{ or } (b=d\text{ and }a\le c), \end{aligned} $$ are linear orders. When applied to your set $X$, these reduce to $$ \begin{aligned} (a,b)L_1(c,d)&\Longleftrightarrow a\le c,\\ (a,b)L_2(c,d)&\Longleftrightarrow b\le d, \end{aligned} $$ since the cases $a=c$ and $b=d$ only arise when $(a,b)=(c,d)$. You can check that both are linear extensions of $R$, that is, that $(a,b)R(c,d)\Longrightarrow (a,b)L_1(c,d)$ and $(a,b)R(c,d)\Longrightarrow (a,b)L_2(c,d)$. You can also check that the intersection of $L_1$ and $L_2$ is $R$.