Decomposition of $2^{[n]}$ into $\binom{n}{n/2}$ chains 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:

*

*$m$ is odd.

*$S_1 \subset S_2 \subset \cdots \subset S_m \subseteq [n]$

*$\forall m \in \{1,...,m-1\}: \; |S_{i+1}|=|S_i|+1$

*$|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.
 A: 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.

*

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


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