Sperner family

Incombinatorics,aSperner family(orSperner system;named in honor ofEmanuel Sperner), orclutter,is afamilyFof subsetsof a finite setEin which none of the sets contains another. Equivalently, a Sperner family is anantichainin the inclusionlatticeover thepower setofE.A Sperner family is also sometimes called anindependent systemorirredundant set.

Sperner families are counted by theDedekind numbers,and their size is bounded bySperner's theoremand theLubell–Yamamoto–Meshalkin inequality.They may also be described in the language ofhypergraphsrather than set families, where they are calledclutters.

Dedekind numbers

The number of different Sperner families on a set ofnelements is counted by theDedekind numbers,the first few of which are

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequenceA000372in theOEIS).

Although accurateasymptoticestimates are known for larger values ofn,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 ofnelements can be organized as afree 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

Thek-element subsets of ann-element set form a Sperner family, the size of which is maximized whenk=n/2 (or the nearest integer to it). Sperner's theoremstates that these families are the largest possible Sperner families over ann-element set. Formally, the theorem states that, for every Sperner familySover ann-element set,

|S|\leq {\binom {n}{\lfloor n/2\rfloor }}.

LYM inequality

TheLubell–Yamamoto–Meshalkin inequalityprovides another bound on the size of a Sperner family, and can be used to prove Sperner's theorem. It states that, ifa_kdenotes the number of sets of sizekin a Sperner family over a set ofnelements, then

\sum _{k=0}^{n}{\frac {a_{k}}{n \choose k}}\leq 1.

Clutters

Aclutteris 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.

In more complicated language, a clutter is ahypergraph $(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). An opposite notion to a clutter is anabstract simplicial complex,where every subset of an edge is contained in the hypergraph; this is anorder idealin the poset of subsets ofV.

If $H=(V,E)$ is a clutter, then theblockerofH,denoted by $b(H)$ ,is the clutter with vertex setVand 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 $\nu (H)$ to be the size of the largest collection of disjoint edges inHand $\tau (H)$ to be the size of the smallest edge in $b(H)$ .It is easy to see that $\nu (H)\leq \tau (H)$ .

Examples

IfGis a simple loopless graph, then $H=(V(G),E(G))$ is a clutter (if edges are treated as unordered pairs of vertices) and $b(H)$ is the collection of all minimalvertex covers.Here $\nu (H)$ is the size of the largest matching and $\tau (H)$ is the size of the smallest vertex cover.Kőnig's theoremstates that, forbipartite graphs, $\nu (H)=\tau (H)$ .However for other graphs these two quantities may differ.
LetGbe a graph and let $s,t\in V(G)$ .The collectionHof all edge-sets ofs-tpaths is a clutter and $b(H)$ is the collection of all minimal edge cuts which separatesandt.In this case $\nu (H)$ is the maximum number of edge-disjoints-tpaths, and $\tau (H)$ is the size of the smallest edge-cut separatingsandt,soMenger's theorem(edge-connectivity version) asserts that $\nu (H)=\tau (H)$ .
LetGbe a connected graph and letHbe the clutter on $E(G)$ consisting of all edge sets of spanning trees ofG.Then $b(H)$ is the collection of all minimal edge cutsets inG.

Minors

There is a minor relation on clutters which is similar to theminor relationon graphs. If $H=(V,E)$ is a clutter and $v\in V$ ,then we maydeletevto get the clutter $H\setminus v$ with vertex set $V\setminus \{v\}$ and edge set consisting of all $A\in E$ which do not containv.Wecontractvto get the clutter $H/v=b(b(H)\setminus v)$ .These two operations commute, and ifJis another clutter, we say thatJis aminorofHif a clutter isomorphic toJmay be obtained fromHby a sequence of deletions and contractions.

References

Anderson, Ian (1987), "Sperner's theorem",Combinatorics of Finite Sets,Oxford University Press, pp. 2–4.
Edmonds, J.;Fulkerson, D. R.(1970), "Bottleneck extrema",Journal of Combinatorial Theory,8(3): 299–306,doi:10.1016/S0021-9800(70)80083-7.
Knuth, Donald E.(2005),"Draft of Section 7.2.1.6: Generating All Trees",The Art of Computer Programming,vol. IV, pp. 17–19.
Sperner, Emanuel(1928),"Ein Satz über Untermengen einer endlichen Menge"(PDF),Mathematische Zeitschrift(in German),27(1): 544–548,doi:10.1007/BF01171114,JFM 54.0090.06.