Partition of lattice into symmetric chains

Question

Let $C_1 \subsetneq C_2 \subsetneq C_3 \subsetneq \cdots \subsetneq C_k$ be a chain in the subset lattice $(2^{[n]},\subseteq)$. A chain is considered symmetric if $|C_1| + |C_k| = n$ and $|C_{i+1}| = |C_i| +1$ for all $i=1,2,\ldots,k-1$. Show that the poset $2^{[n]}$ can be partitioned into $C\left(n,\lfloor n/2 \rfloor\right)$ pairwise disjoint symmetric chains.

Answer 1

I will assume $n$ is even. The odd case is similar, but harder to write out explicitly.

First partition the subset lattice into the subsets $A_k$ containing subsets of $2^{n}$ of length $k$. Now, $|A_{n/2}| = {n \choose n/2}$ and it will be our goal to find a correspondence between symmetric pairwise disjoint chains and $A_{n/2}$.

We will use the following observation: given any element $\alpha \in A_{n/2}$ there is a bijection $\phi_{\alpha}$ between the proper subsets of $\alpha$ and proper supersets of $\alpha$. Therefore we can use the following "greedy" algorithm: pick an element $\alpha \in A_{n/2}$. Extend it to a chain as long as possible by picking the not-already-used elements from the lower levels $A_k$, $k < n/2$ and the corresponding (under $\phi_{\alpha}$) elements from the upper levels. Cross out these elements (so that we won't use them again and the constructed chains are pairwise disjoint). Continue in the same manner until all $n \choose n/2$ chains are constructed. We only need to prove that this process doesn't stop early. But this is simple because the function $|A_k|$ is decreasing from $k=n/2$ to $k=0$, so that if there is nothing to choose from at level $j$ it is because all the elements of $A_j$ (and lower levels) and already crossed out.

Illustration of the algorithm for $n=4$. We denote the elements by $\{a,b,c,d\}$, so that $A_2 = \{ab, ac, ad, bc, bc, cd\}$ (I am denoting subsets by concatenation to ease writing). First we pick $ab$ and extend it to chain $C_0 = \emptyset \subset a \subset ab \subset abc \subset abcd$. Next we go to $ac$ and extend it to $C_1 = c \subset ac \subset acd$. Continuing in this manner we get $C_2 = d \subset ad \subset abd$, $C_3 = b \subset bc \subset bcd$, $C_4 = bd$ and $C_5 = cd$.

Answer 2

There is already one answer, so I will try to present a different approach and some intuition. The Hasse diagram of your lattice is $n$-dimensional hypercube. Your claim is equivalent to that this cube can be covered with $\binom{n}{n/2}$ disjoint (directed) paths.

Some thing to think of: if you were to create a largest family $\mathcal{F}$ of incomparable elements, then it would have size $\binom{n}{n/2}$, that is the family of all the sets of size $\frac{n}{2}$.

$$\mathcal{F} = \Big\{ A \in 2^{[n]} \ \Big|\ \frac{n}{2} = |A| \Big\}.$$

Any two different are incomparable, because they have the same size. Moreover, any other set $A$ would have some comparable element in this family. If $|A| < n/2$ then there would be $B \in \mathcal{F}$ such that $A \subset B$ and if $|A| > n/2$ then there would be $B \in \mathcal{F}$ such that $B \subset A$. (Of course, this is not a proof that $\mathcal{F}$ is the biggest, only that $\mathcal{F}$ is maximal.)

Now, to create $\binom{n}{n/2}$ disjoint paths, we start with vertices corresponding to $\mathcal{F} = \mathcal{F}_{n/2}$ and work two ways: towards $\varnothing$ (with functions $f$) and towards $[n]$ (with functions $g$). Set

$$\mathcal{F}_k = \Big\{ A \in 2^{[n]} \ \Big|\ k = |A| \Big\}.$$

For $k \leq \frac{n}{2}$ let $f_{k} : \mathcal{F}_{k-1} \to \mathcal{F}_{k}$ be any injection such that $A \subset f(A)$, similarly, for $k \geq \frac{n}{2}$ let $g_{k} : \mathcal{F}_{k+1} \to \mathcal{F}_{k}$ be any injection such that $g(A) \subset A$. The proof that such functions exist is easy, quite natural and tedious, so I will skip it here.

To create a path, pick any vertex $A \in 2^{[n]}$ such that $|A| < \frac{n}{2}$ and follow $$A,\ \ f_{|A|}(A),\ \ f_{|A|+1}(f_{|A|}(A)),\ \ f_{|A|+2}(f_{|A|+1}(f_{|A|}(A))),\ \ldots,$$ or pick $B \in 2^{[n]}$ with $|B| > \frac{n}{2}$ and follow $B, g(B), g(g(B)), \ldots$, until you reach $\mathcal{F}$. Any vertex $A$ or $B$ is covered because it belongs to $\mathcal{F}_{|A|}$ or $\mathcal{F}_{|B|}$, and $f$ and $g$ are injective, therefore, the resulting paths are disjoint. Moreover, any vertex is connected via some path to an element of $\mathcal{F}$, but $|\mathcal{F}| = \binom{n}{n/2}$, hence, there are at most $\binom{n}{n/2}$ paths total. Finally, each element of $\mathcal{F}$ creates one path (possibly $1$-vertex, $0$-edges path, but still), so there are exactly $\binom{n}{n/2}$ paths and this concludes the proof.

I hope this helps ;-)