Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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$.

share|improve this answer

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 ;-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.