# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Sperner family

In combinatorics, a Sperner family (or Sperner system), named in honor of Emanuel Sperner, is a set system (F, E) in which no element is contained in another. Formally,

If X, Y are in F and XY, then X is not contained in Y and Y is not contained in X.

Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system.

 Contents

## Sperner's theorem

One interesting and useful result is the following, known as Sperner's theorem.

For every Sperner family S over an n-set,

$|S| \le {n \choose \lfloor{n/2}\rfloor}.$

### Proof

The following proof is due to Lubell. (see reference). Let sk denote the number of k-sets in S. For all 0 ≤ k ≤ n,

${n \choose \lfloor{n/2}\rfloor} \ge {n \choose k}$

and, thus,

${s_k \over {n \choose \lfloor{n/2}\rfloor}} \le {s_k \over {n \choose k}}.$

Since S is an antichain, we can sum over the above inequality from k = 0 to n and then apply the LYM inequality to obtain

$\sum_{k=0}^n{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le \sum_{k=0}^n{s_k \over {n \choose k}} \le 1,$

which means

$|S| = \sum_{k=0}^n s_k \le {n \choose \lfloor{n/2}\rfloor}$.

This completes the proof.

Sperner's theorem can be seen as a special case of Dilworth's theorem. It is sometimes called Sperner's lemma, but unfortunately, this name also refers to another result on coloring. To differentiate the two results, the above is more commonly known as simply Sperner's theorem nowadays.

## References

Lubell, D. (1966). A short proof of Sperner's theorem, J. Combin. Theory 1, 299.