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

## External links

Last updated: 08-30-2005 06:55:30
03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice