Sperner Family - Sperner's Theorem

The k-element subsets of an n-element set form a Sperner family, the size of which is maximized when k = n/2 (or the nearest integer to it). Sperner's theorem states that these families are the largest possible Sperner families over an n-element set. Formally, the theorem states that, for every Sperner family S over an n-element set,

Another way of stating this result is that the partial order width of the inclusion lattice over a power set is . This result is sometimes called Sperner's lemma, but the name "Sperner's lemma" also refers to an unrelated result on coloring triangulations. To differentiate the two results, the result on the size of a Sperner family is now more commonly known as Sperner's theorem.

A graded partially ordered set is said to have the Sperner property when one of its largest antichains is formed by a set of elements that all have the same rank; Sperner's theorem states that the poset of all subsets of a finite set, partially ordered by set inclusion, has the Sperner property.