## Section6.5The Subset Lattice

When $$X$$ is a finite set, the family of all subsets of $$X\text{,}$$ partially ordered by inclusion, forms a subset lattice 1 . We illustrate this in Figure 6.26 where we show the lattice of all subsets of $$\{1,2,3,4\}\text{.}$$ In this figure, note that we are representing sets by bit strings, and we have further abbreviated the notation by writing strings without commas and parentheses.

A lattice is a special type of poset. You do not have to concern yourself with the definition and can safely replace “lattice” with “poset” as you read this chapter.

For a positive integer $$t\text{,}$$ we let $$\bftwo^t$$ denote the subset lattice consisting of all subsets of $$\{1,2,\dots,t\}$$ ordered by inclusion. Some elementary properties of this poset are:

1. The height is $$t+1$$ and all maximal chains have exactly $$t+1$$ points.

2. The size of the poset $$\bftwo^t$$ is $$2^t$$ and the elements are partitioned into ranks (antichains) $$A_0, A_1,\dots, A_t$$ with $$|A_i|=\binom{t}{i}$$ for each $$i=0,1,\dots,t\text{.}$$

3. The maximum size of a rank in the subset lattice occurs in the middle, i.e. if $$s=\lfloor t/2\rfloor\text{,}$$ then the largest binomial coefficient in the sequence $$\binom{t}{0}, \binom{t}{1},\binom{t}{2},\dots,\binom{t}{t}$$ is $$\binom{t}{s}\text{.}$$ Note that when $$t$$ is odd, there are two ranks of maximum size, but when $$t$$ is even, there is only one.

### Subsection6.5.1Sperner's Theorem

For the width of the subset lattice, we have the following classic result of Sperner.

The width of the poset $$\bftwo^t$$ is at least $$C(t,\lfloor\frac{t}{2}\rfloor)$$ since the set of all $$\lfloor\frac{t}{2}\rfloor$$-element subsets of $$\{1,2,\dots,t\}$$ is an antichain. We now show that the width of $$\bftwo^t$$ is at most $$C(t,\lfloor\frac{t}{2}\rfloor)\text{.}$$

Let $$w$$ be the width of $$\bftwo^t$$ and let $$\{S_1,S_2,\dots, S_w\}$$ be an antichain of size $$w$$ in this poset, i.e., each $$S_i$$ is a subset of $$\{1,2,\dots,t\}$$ and if $$1\le i\lt j\le w\text{,}$$ then $$S_i\nsubseteq S_j$$ and $$S_j\nsubseteq S_i\text{.}$$

For each $$i\text{,}$$ consider the set $$\cgS_i$$ of all maximal chains which pass through $$S_i\text{.}$$ It is easy to see that if $$|S_i|=k_i\text{,}$$ then $$|\cgS_i|=k_i!(t-k_i)!\text{.}$$ This follows from the observation that to form such a maximum chain beginning with $$S_i$$ as an intermediate point, you delete the elements of $$S_i$$ one at a time to form the sets of the lower part of the chain. Also, to form the upper part of the chain, you add the elements not in $$S_i$$ one at a time.

Note further that if $$1\le i \lt j\le w\text{,}$$ then $$\cgS_i\cap \cgS_j =\emptyset\text{,}$$ for if there was a maximum chain belonging to both $$\cgS_i$$ and $$\cgS_j\text{,}$$ then it would imply that one of $$S_i$$ and $$S_j$$ is a subset of the other.

Altogether, there are exactly $$t!$$ maximum chains in $$\bftwo^t\text{.}$$ This implies that

\begin{equation*} \sum_{i=1}^{w} k_i!(t-k_i)!\le t!\text{.} \end{equation*}

This implies that

\begin{equation*} \sum_{i=1}^{w}\frac{k_i!(t-k_i)!}{t!}= \sum_{i=1}^{w}\frac{1}{\binom{t}{k_i}}\le 1. \end{equation*}

It follows that

\begin{equation*} \sum_{i=1}^{i=w}\frac{1}{\binom{t}{\lceil\frac{t}{2}\rceil}}\le 1\text{.} \end{equation*}

Thus

\begin{equation*} w\le \binom{t}{\lceil\frac{t}{2}\rceil}\text{.} \end{equation*}