I am trying to do exercise in this book (page 54, number 3.11). The question :
Find orthogonal chain decomposition as required in the proof of theorem from Shearer & Kleitman for $n=3$ and $n=4$.
Theorem (Shearer and Kleitman 1979)
If $n \geq 2$, there exist two orthogonal chain decompositions of the poset of subsets of an $n$-set into $\binom {n}{[n/2]}$ chains.
Some definitions : Suppose we can find two chain decompositions of $P$ (we define $P$ as partial order set) into $m$ chains with the property that no pair elements of $P$ in the same chain in one of the decompositions lies in the same chain in the second decomposition (such a pair of chain decompositions are said to be orthogonal).
I know that for $n=3$, chain decomposition will be :
$\emptyset \subset \{1\} \subset \{12\} \subset \{123\}$
$\{2\} \subset \{23\}$
$\{3\} \subset \{13\}$
For $n=4$, it has 6 chain decompoitions. Then how to find orthogonal chain decomposition for $n=3$ and $n=4$ ?
(At long last getting this off the unanswered list.)
In a chain decomposition for $n=3$ that is orthogonal to yours, $\varnothing$, $\{1\}$, $\{1,2\}$, and $\{1,2,3\}$ must all go into different chains, so the decomposition must have (at least) four chains. The remaining four subsets of $\{1,2,3\}$ are $\{2\}$, $\{3\}$, $\{1,3\}$, and $\{2,3\}$, and we can begin by trying to add one of them to each of the four chains that we’ve started.
The only one that can be added to $\{1\}$ is $\{1,3\}$, giving us a chain $\{1\}\subset\{1,3\}$, and the only one that can be added to $\{1,2\}$ is $\{2\}$, giving us a chain $\{2\}\subset\{1,2\}$. Each of $\{3\}$ and $\{2,3\}$ can be added to either of the remaining chains, so we get the chain decompositions
$$\begin{align*} \varnothing&\subset\{3\}\\ \{1\}&\subset\{1,3\}\\ \{2\}&\subset\{1,2\}\\ \{2,3\}&\subset\{1,2,3\} \end{align*}$$
and
$$\begin{align*} \varnothing&\subset\{2,3\}\\ \{1\}&\subset\{1,3\}\\ \{2\}&\subset\{1,2\}\\ \{3\}&\subset\{1,2,3\}\,. \end{align*}$$
For that matter, we could add both $\{3\}$ and $\{2,3\}$ to either of the remaining chains to get the chain decompositions
$$\begin{align*} &\varnothing\subset\{3\}\subset\{2,3\}\\ &\{1\}\subset\{1,3\}\\ &\{2\}\subset\{1,2\}\\ &\{1,2,3\} \end{align*}$$
and
$$\begin{align*} &\varnothing\\ &\{1\}\subset\{1,3\}\\ &\{2\}\subset\{1,2\}\\ &\{3\}\subset\{2,3\}\subset\{1,2,3\}\,. \end{align*}$$
Each of these is easily seen to be orthogonal to yours.
For $n=4$ we can start with the symmetric chain decomposition of Example $\mathbf{3.1.1}$:
$$\begin{align*} &\{3,4\}\\ &\{2,4\}\\ &\{4\}\subset\{1,4\}\subset\{1,2,4\}\\ &\{3\}\subset\{1,3\}\subset\{1,3,4\}\\ &\{2\}\subset\{2,3\}\subset\{2,3,4\}\\ &\varnothing\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\subset\{1,2,3,4\}\,. \end{align*}\tag{1}$$
Now we can apply the algorithm in the proof of Theorem $\mathbf{3.4.6}$. We first replace each set by its relative complement in $\{1,2,3,4\}$ to get
$$\begin{align*} &\{1,2\}\\ &\{1,3\}\\ &\{3\}\subset\{2,3\}\subset\{1,2,3\}\\ &\{2\}\subset\{2,4\}\subset\{1,2,4\}\\ &\{1\}\subset\{1,4\}\subset\{1,3,4\}\\ &\varnothing\subset\{4\}\subset\{3,4\}\subset\{2,3,4\}\subset\{1,2,3,4\}\,. \end{align*}$$
This is almost orthogonal to $(1)$: the only problem is that $\varnothing$ and $\{1,2,3,4\}$ are in the same chain. Following the algorithm in the proof, we simply move $\varnothing$ to any chain that does not contain any of the sets $\{1\}$, $\{1,2\}$, $\{1,2,3\}$, and $\{1,2,3,4\}$, i.e., to either the second or the fourth chain. Moving it to the second chain gives us the decomposition
$$\begin{align*} &\{1,2\}\\ &\varnothing\subset\{1,3\}\\ &\{3\}\subset\{2,3\}\subset\{1,2,3\}\\ &\{2\}\subset\{2,4\}\subset\{1,2,4\}\\ &\{1\}\subset\{1,4\}\subset\{1,3,4\}\\ &\{4\}\subset\{3,4\}\subset\{2,3,4\}\subset\{1,2,3,4\}\,, \end{align*}$$
which is indeed orthogonal to $(1)$.