Sperner family

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,

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

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 a_k denotes the number of sets of size k in a Sperner family over a set of n elements, then

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

1. If G is a simple loopless graph, then ${\displaystyle H=(V(G),E(G))}$ is a clutter (if edges are treated as unordered pairs of vertices) and ${\displaystyle b(H)}$ is the collection of all minimal vertex covers. Here ${\displaystyle \nu (H)}$ is the size of the largest matching and ${\displaystyle \tau (H)}$ is the size of the smallest vertex cover. Kőnig's theorem states that, for bipartite graphs, ${\displaystyle \nu (H)=\tau (H)}$. However for other graphs these two quantities may differ.
2. Let G be a graph and let ${\displaystyle s,t\in V(G)}$. The collection H of all edge-sets of s-t paths is a clutter and ${\displaystyle b(H)}$ is the collection of all minimal edge cuts which separate s and t. In this case ${\displaystyle \nu (H)}$ is the maximum number of edge-disjoint s-t paths, and ${\displaystyle \tau (H)}$ is the size of the smallest edge-cut separating s and t, so Menger's theorem (edge-connectivity version) asserts that ${\displaystyle \nu (H)=\tau (H)}$.
3. Let G be a connected graph and let H be the clutter on ${\displaystyle E(G)}$ consisting of all edge sets of spanning trees of G. Then ${\displaystyle b(H)}$ is the collection of all minimal edge cutsets in G.

There is a minor relation on clutters which is similar to the minor relation on graphs. If ${\displaystyle H=(V,E)}$ is a clutter and ${\displaystyle v\in V}$, then we may delete v to get the clutter ${\displaystyle H\setminus v}$ with vertex set ${\displaystyle V\setminus \{v\}}$ and edge set consisting of all ${\displaystyle A\in E}$ which do not contain v. We contract v to get the clutter ${\displaystyle 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.