Sperner family


In combinatorics, a Sperner family, or clutter, is a family F of subsets of a finite set E in which none of the sets contains 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 irredundant set.
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
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.
The collection of all Sperner families on a set of n elements can be organized as a free distributive lattice, in which the join of two Sperner families is obtained from the union of the two families by removing sets that are a superset of another set in the union.

Bounds on the size of a 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.
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 is a family of subsets of a finite set such that none contains any other; that is, it is a Sperner family. The difference is in the questions typically asked. Clutters are an important structure in the study of combinatorial optimization.
If is a clutter, then the blocker of H, denoted by, is the clutter with vertex set V and edge set consisting of all minimal sets so that for every. It can be shown that , so blockers give us a type of duality. We define to be the size of the largest collection of disjoint edges in H and to be the size of the smallest edge in. It is easy to see that.

Examples

  1. If G is a simple loopless graph, then is a clutter and is the collection of all minimal vertex covers. Here is the size of the largest matching and is the size of the smallest vertex cover. Kőnig's theorem states that, for bipartite graphs,. However for other graphs these two quantities may differ.
  2. Let G be a graph and let. The collection H of all edge-sets of s-t paths is a clutter and is the collection of all minimal edge cuts which separate s and t. In this case is the maximum number of edge-disjoint s-t paths, and is the size of the smallest edge-cut separating s and t, so Menger's theorem asserts that.
  3. Let G be a connected graph and let H be the clutter on consisting of all edge sets of spanning trees of G. Then is the collection of all minimal edge cutsets in G.

    Minors

There is a minor relation on clutters which is similar to the minor relation on graphs. If is a clutter and, then we may delete v to get the clutter with vertex set and edge set consisting of all which do not contain v. We contract v to get the clutter. These two operations commute, and if J is another clutter, we say that J is a minor of H if a clutter isomorphic to J may be obtained from H by a sequence of deletions and contractions.