Sperner family

Sperner family

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,

If X, Y are in F and XY, then X is not contained in Y and Y is not contained in X.

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.

Contents

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 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-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) 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,

|S| \le {n \choose \lfloor{n/2}\rfloor}.

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.

Proof

The following proof is due to Lubell (see reference). Let sk denote the number of k-sets in S. For all 0 ≤ kn,

{n \choose \lfloor{n/2}\rfloor} \ge {n \choose k}

and, thus,

{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le {s_k \over {n \choose k}}.

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

\sum_{k=0}^n{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le \sum_{k=0}^n{s_k \over {n \choose k}} \le 1,

which means

 |S| = \sum_{k=0}^n s_k \le {n \choose \lfloor{n/2}\rfloor}.

This completes the proof.

Clutters

A clutter H is a hypergraph (V,E), with the added property that A \not\subseteq B whenever A,B \in E and A \neq B (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 H = (V,E) is a clutter, then the blocker of H, denoted b(H), is the clutter with vertex set V and edge set consisting of all minimal sets B \subseteq V so that B \cap A \neq \varnothing for every A \in E. It can be shown that b(b(H)) = H (Edmonds & Fulkerson 1970), so blockers give us a type of duality. We define ν(H) to be the size of the largest collection of disjoint edges in H and τ(H) to be the size of the smallest edge in b(H). It is easy to see that \nu(H) \le \tau(H).

Examples

  1. If G is a simple loopless graph, then H = (V(G),E(G)) is a clutter and b(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.
  2. Let G be a graph and let s,t \in V(G). Define H = (V,E) by setting V = E(G) and letting E be the collection of all edge-sets of s-t paths. Then H is a clutter, and b(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).
  3. 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. Then b(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 H = (V,E) is a clutter and v \in V, then we may delete v to get the clutter H \setminus v with vertex set 
V \setminus \{v\} and edge set consisting of all A \in E which do not contain v. We contract v to get the clutter H / v = b(b(H) \setminus v). 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.

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Famille de Sperner — En combinatoire, une famille de Sperner (ou système de Sperner), appelé en l honneur d Emanuel Sperner, est un hypergraphe (E, F) (c est à dire un ensemble E et un ensemble F de parties de E) dans lequel aucun élément de F ne contient un autre.… …   Wikipédia en Français

  • Satz von Sperner — Der Satz von Sperner ist ein mathematischer Lehrsatz, welcher der diskreten Mathematik zugerechnet wird. Er wurde von Emanuel Sperner im Jahr 1928 veröffentlicht. Der Satz behandelt den engen Zusammenhang zwischen den Antiketten der Potenzmenge… …   Deutsch Wikipedia

  • Lubell-Yamamoto-Meshalkin inequality — In combinatorial mathematics, the Lubell Yamamoto Meshalkin inequality, more commonly known as the LYM inequality, is an inequality on the sizes of sets in a Sperner family, proved by harvtxt|Bollobás|1965, harvtxt|Lubell|1966,… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Dedekind number — …   Wikipedia

  • James Farragher — James F. Farragher (1876 – unknown) was a powerful left tackle for the University of Notre Dame football team in the early 1900s. He is often identified in official university histories as the team s head coach for the 1902 ndash;1903 season.… …   Wikipedia

  • 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. It is named for the mathematician …   Wikipedia

  • Depression (differential diagnoses) — Neuroimaging can be a valuable tool in the diagnostic work up of various psychiatric disorders including depression.[1] Depression, one of the most commonly diagnosed psychiatric disorders,[2][ …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”