## 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!. \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 \end{equation*}

Thus

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