In combinatorics, a Sperner family (or Sperner system), named in honor of Emanuel Sperner, is a family of sets (F, E) in which none of the sets is contained in another. 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 or a clutter.
Contents
Sperner families are counted by the Dedekind numbers, and their size is bounded by Sperner's theorem and the Lubell–Yamamoto–Meshalkin inequality. They may also be described in the language of hypergraphs rather than set families, where they are called clutters.
Dedekind numbers
The number of different Sperner families on a set of n elements is counted by the Dedekind numbers, the first few of which are
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in the OEIS).Although accurate asymptotic estimates are known for larger values of n, it is unknown whether there exists an exact formula that can be used to compute these numbers efficiently.
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,
LYM inequality
The Lubell–Yamamoto–Meshalkin inequality provides another bound on the size of a Sperner family, and can be used to prove Sperner's theorem. It states that, if ak denotes the number of sets of size k in a Sperner family over a set of n elements, then
Clutters
A clutter H is a hypergraph
If
Examples
- If G is a simple loopless graph, then
H = ( V ( G ) , E ( G ) ) is a clutter andb ( H ) is the collection of all minimal vertex covers. Hereν ( H ) is the size of the largest matching andτ ( H ) is the size of the smallest vertex cover. König's theorem states that, for bipartite graphs,ν ( H ) = τ ( H ) . However for other graphs these two quantities may differ. - Let G be a graph and let
s , t ∈ V ( G ) . DefineH = ( V , E ) by settingV = E ( G ) and letting E be the collection of all edge-sets of s-t paths. Then H is a clutter, andb ( H ) is the collection of all minimal edge cuts which separate s and t. In this caseν ( H ) is the maximum number of edge-disjoint s-t paths, andτ ( H ) is the size of the smallest edge-cut separating s and t, so Menger's theorem (edge-connectivity version) asserts thatν ( H ) = τ ( H ) . - Let G be a connected graph and let H be the clutter on
E ( G ) consisting of all edge sets of spanning trees of G. Thenb ( H ) is the collection of all minimal edge cuts in G.
Minors
There is a minor relation on clutters which is similar to the minor relation on graphs. If