Decomposition of $2^{[n]}$ into $\binom{n}{n/2}$ chains

Question

I am struggling with this problem:

Let n be an even number, and denote $[n]=\{1,2,...,n\}$. A sequence of sets $S_1 , S_2 , \cdots , S_m \subseteq [n]$ is considered graceful if:

1. $m$ is odd.
2. $S_1 \subset S_2 \subset \cdots \subset S_m \subseteq [n]$
3. $\forall m \in \{1,...,m-1\}: \; |S_{i+1}|=|S_i|+1$
4. $|S_m|+|S_1|=n$

Show that it is possible to decompose the $2^n$ subsets of $[n]$ using $\binom{n}{n/2}$ graceful chains. Different chains may be of different lengths. Every subset of $[n]$ must appear in one, and only one, chain.

I have figured that $$|S_1|=\frac{n-m+1}{2}, \; |S_i|=\frac{n-m+2i-1}{2}$$ for any valid choice of $m$. In addition, it suggests $m\in\{1,3,...,n+1\}$. It is also clear that one of the chains must be $$\emptyset\subset\{1\}\subset\{1,2\}\subset\cdots\subset\{1,...,n\}$$ where all the inner sets in this chain may be chosen arbitrary.

I would appreciate any help.

Answer 1

Seeing that Mike Earnest has already provided some nice references and also a principled way of constructing a graceful decomposition, I'll just post some of my remarks.

1. It can be seen that middle element of every chain has to be a subset of $[n]$ with size $n / 2$. That is, for a chain of size $m$, $|S_{(m + 1)/2}| = n / 2$. Since any chain includes some $S_m$ with $|S_m| = n / 2$ and furthermore every one of the ${n \choose n / 2}$ subsets of size $n/2$ is included in exactly one chain, any graceful decomposition actually must have ${n \choose n / 2}$ chains.

2. I believe there is a simple way to construct the chains. Let us construct the digraph $G$, whose vertices $S_i$ are subsets of $[n]$ and there is an edge from $S_i$ to $S_j$ if and only if $S_i \subset S_j$ and $|S_j| = |S_i| + 1$. Initialize $\Sigma = V(G)$, then do the following:

• Find an element $\sigma \in \Sigma$ of smallest size; if $\Sigma$ is empty, then the algorithm terminates. Suppose $|\sigma| = k$. We will construct a chain where $\sigma$ is the first element of the chain. Initialize $i = k + 1$.
• While $i \leq n - k$, choose any $\sigma_{i+1}$ that is an outneighbor of $\sigma_i$ to be the next element of the chain. Increment $i$ and remove $\sigma_i$ from $\Sigma$.

The correctness of this provided algorithm relies on a couple facts. The four properties of graceful chains can easily be verified for this algorithm. Furthermore, every element is included once and exactly once in some chain, as every element is initially in $\Sigma$ and is removed when it is added to a chain (the algorithm does not stop until $\Sigma$ is empty).

The slightly tricky part is explain why the algorithm never gets stuck. Namely, we have to prove that in the second bullet point, we can always find an outneighbor $\sigma_{i+1}$ of $\sigma_{i}$ if $i < n - k$. Suppose the opposite, namely that at some point in the algorithm we encounter a $\sigma_i$ without an outneighbor $\sigma_{i+1}$ that hasn't already been used. Note that $|\sigma_i| = i$ and $\sigma_{i}$ has $n - i$ outneighbors. For this bad scenario to happen, we must have created at least $n - i$ chains, each with some element $\sigma$ where $|\sigma| = i$. Of course, any chain with an element of size $i$ must also have an element of size $n - i$, as it was previously established that every chain's middle element is of size $n/2$.

Here is the crucial fact: the number of subsets of $2^{[n]}$ of size $i$ is exactly equal to the number of subsets of size $n - i$, so in fact it must have been the case that before this iteration of the algorithm, all subsets of length $i$ had been included in a chain we built already. (Note that here it is important to note that all chains created by the algorithm are graceful.) But this contradicts the fact that $\sigma_i$, which has size $i$, has not been included in a chain. $\square$

Answer 2

What you are constructing is known in the literature as a symmetric chain decomposition of the partially ordered set of the subsets of $[n]$. I will therefore use "symmetric" instead of "graceful" throughout.

---

There is an explicit solution using the Catalan factorization, which I learned from this paper by Ömer Eğecioğlu and Alastair King. Identify subsets of $[n]$ with sequences of length $n$ with entries in $\{0,1\}$. The Catalan factorization is obtained as follows:

1. First, underline any two entries which are a $1$ followed by a $0$ with only underlined entries between. Repeat this step until no such entries remain.

2. Now, the entries which are not underlined will consist of some number of $0$'s, followed by some number of $1$'s. If not, we would not be done with step $1$.

3. Finally, any entry which is not underlined is replaced with a new symbol, $z$. Furthermore, the number of $1$'s which converted to $z$'s is recorded as a number $k$. This final result, consisting of the $(0,1,z)-$sequence and the number $k$, is the Catalan factorization.

Note that you can recover the original binary word from the Catalan factorization by replacing the last $k$ instances of $z$ with a $1$, and all other $z$'s with a $0$.

I will give an example shortly, but let me first say how the Catalan factorization gives a graceful chain decomposition. We can think of the Catalan factorization as an ordered pair $(w,k)$, where $w$ is the $(0,1,z)-$ sequence, and $k$ is the number of $z$'s which represent $1$'s. Two subsets are in the same composition when they have they same word $w$ for their Catalan factorization. That is, for every sequence $w$ where the number of $z$'s is $m$, then $$ (w,0)\subset (w,1)\subset\dots\subset (w,m) $$ represents a symmetric chain of subsets.

---

Example: With $n=15$, consider the subset $$\{2,3,5,9,10,13,14,15\}$$

This corresponds to the binary sequence $$ 011010001100111 $$ where the $i^{th}$ entry being $1$ means $i$ is in the subset. We first underline all instance of a $1$ immediately followed by a $0$: $$ 01\underline{1010}001\underline{10}0111 $$ This creates more pairs of $1$s followed by $0$s with only underlined entries between, so we continue: $$ 0\underline{110100}0\underline{1100}111 $$ Now, all the non-underlined zeroes occur before all non-underlined ones, so we are done. We finish by replacing all non-underline entries with a $z$, and writing down the number of $1$s: $$ z110100z1100zzz,\qquad k=3 $$ Therefore, this subset will be in a symmetric chain of length $6$, corresponding the the subsets formed by keeping the word the same, while replacing $k$ with the numbers between $0$ and $5$ inclusive. This is illustrated below: $$ \begin{array}{c|c|c} k& \text{binary word} & \text{subset}\\ \hline 0 & 0\underline{110100}0\underline{1100}000 & \{2,3,5,9,10\}\\ 1 & 0\underline{110100}0\underline{1100}001 & \{2,3,5,9,10,15\}\\ 2 & 0\underline{110100}0\underline{1100}011 & \{2,3,5,9,10,14,15\}\\ 3 & 0\underline{110100}0\underline{1100}111 & \{2,3,5,9,10,13,14,15\}\\ 4 & 0\underline{110100}1\underline{1100}111 & \{2,3,5,8,9,10,13,14,15\}\\ 5 & 1\underline{110100}1\underline{1100}111 & \{1,2,3,5,8,9,10,13,14,15\}\\ \end{array} $$