Sperner family
Encyclopedia
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,
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, if viewed from the hypergraph perspective, a clutter.
s, 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.
Sperner's theorem (a special case of Dilworth's theorem
) states that these families are the largest possible Sperner families over an n-set. Formally, the theorem states that, for every Sperner family S over an n-set,
It is sometimes called Sperner's lemma
, but that name also refers to another result on coloring. 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.
and, thus,
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
which means
This completes the proof.
, with the added property that 
whenever 
and 
(i.e. no edge properly contains another). That is, the sets of vertices represented by the hyperedges form a Sperner family. Clutters are an important structure in the study of combinatorial optimization. The opposite notion of a clutter is an abstract simplicial complex
, where every subset of an edge is contained in the hypergraph.
If
is a clutter, then the blocker of H, denoted 
, 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 
.
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.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, a Sperner family (or Sperner system), named in honor of Emanuel Sperner
Emanuel Sperner
Emanuel Sperner was a German mathematician, best known for two theorems. He was born in Waltdorf , and died in Sulzburg-Laufen, Germany. He was a student at Hamburg University where his advisor was Wilhelm Blaschke...
, is a set system
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
(F, E) in which no element is contained in another. Formally,
- If X, Y are in F and X ≠ Y, then X is not contained in Y and Y is not contained in X.
Equivalently, a Sperner family is an antichain
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
in the inclusion lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
over the power set of E. A Sperner family is also sometimes called an independent system or, if viewed from the hypergraph perspective, a clutter.
Dedekind numbers
The number of different Sperner families on a set of n elements is counted by the Dedekind numberDedekind number
Image:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right| The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively...
s, the first few of which are
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 .
Although accurate asymptotic
Asymptotic expansion
In mathematics an asymptotic expansion, asymptotic series or Poincaré expansion is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular,...
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-subsets of an n-set form a Sperner family, the size of which is maximized when k = n/2.Sperner's theorem (a special case of Dilworth's theorem
Dilworth's theorem
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains...
) states that these families are the largest possible Sperner families over an n-set. Formally, the theorem states that, for every Sperner family S over an n-set,
It is sometimes called Sperner's lemma
Sperner's lemma
In mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which follows from it. Sperner's lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors...
, but that name also refers to another result on coloring. 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
Graded poset
In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...
partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
is said to have the Sperner property
Sperner property of a partially ordered set
In the order-theoretic mathematics, a graded partially ordered set is said to have the Sperner property , if no antichain within it is larger than the largest rank level in the poset.Since every rank level is itself an antichain, the Sperner property is equivalently the property that some rank...
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.
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,and, thus,
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
which means
This completes the proof.
Clutters
A clutter H is a hypergraphHypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
, with the added property that whenever and (i.e. no edge properly contains another). That is, the sets of vertices represented by the hyperedges form a Sperner family. Clutters are an important structure in the study of combinatorial optimization. The opposite notion of a clutter is an abstract simplicial complexAbstract simplicial complex
In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets...
, where every subset of an edge is contained in the hypergraph.
If
is a clutter, then the blocker of H, denoted , 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
- If G is a simple loopless graph, then
is a clutter and 
is the collection of all minimal vertex coverVertex coverIn the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
s. Here
is the size of the largest matching and 
is the size of the smallest vertex cover. König's theoremKönig's theorem (graph theory)In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...
states that, for bipartite graphBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
s,
. However for other graphs these two quantities may differ. - Let G be a graph and let
. Define 
by setting 
and letting E be the collection of all edge-sets of s-t paths. Then H 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 theoremMenger's theoremIn the mathematical discipline of graph theory and related areas, Menger's theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge-connectivity and vertex-connectivity by Karl Menger in 1927...
(edge-connectivity version) asserts that
. - 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 cuts in G.
Minors
There is a minor relation on clutters which is similar to the minor relationMinor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
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.External links
- Sperner's Theorem at cut-the-knotCut-the-knotCut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
- Sperner Theory by Konrad Engel.
- Sperner's theorem on the polymath1 wiki