|
|
|
|
Sperner's theorem
|
(Theorem)
|
|
|
What is the size of the largest family $\mathcal{F}$ of subsets of an $n$ -element set such that no $A\in \mathcal{F}$ is a subset of $B\in \cal{F}$ ? Sperner [3] gave an answer in the following elegant theorem:
Theorem 1 For every family $\mathcal{F}$ of incomparable subsets of an $n$ -set, $\abs{\mathcal{F}}\leq \binom{n}{\floor{n/2}}$ .
A family satisfying the conditions of Sperner's theorem is usually called Sperner family or antichain. The later terminology stems from the fact that subsets of a finite set ordered by inclusion form a Boolean lattice.
There are many generalizations of Sperner's theorem. On one hand, there are refinements like LYM inequality that strengthen the theorem in various ways. On the other hand, there are generalizations to posets other than the Boolean lattice. For a comprehensive exposition of the topic one should consult a well-written monograph by Engel[2].
- 1
- Béla Bollobás.
Combinatorics: Set systems, hypergraphs, families of vectors, and combinatorial probability.
1986.
Zbl 0595.05001.
- 2
- Konrad Engel.
Sperner theory, volume 65 of Encyclopedia of Mathematics and Its Applications.
Cambridge University Press.
Zbl 0868.05001.
- 3
- Emanuel Sperner.
Ein Satz über Untermengen einer endlichen Menge.
Math. Z., 27:544-548, 1928.
Available online at JFM.
|
"Sperner's theorem" is owned by bbukh.
|
|
(view preamble | get metadata)
See Also: LYM inequality
| Also defines: |
Sperner family |
| Keywords: |
antichain, maximal antichain |
|
|
Cross-references: posets, LYM inequality, Boolean lattice, inclusion, finite set, antichain, incomparable, theorem, subsets, size
There is 1 reference to this entry.
This is version 4 of Sperner's theorem, born on 2003-08-17, modified 2005-01-01.
Object id is 4606, canonical name is SpernersTheorem.
Accessed 5126 times total.
Classification:
| AMS MSC: | 05D05 (Combinatorics :: Extremal combinatorics :: Extremal set theory) | | | 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
