Sperner's theorem

Last updated December 07, 2024

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

Statement

A family of sets in which none of the sets is a strict subset of another is called a Sperner family, or an antichain of sets, or a clutter. For example, the family of k-element subsets of an n-element set is a Sperner family. No set in this family can contain any of the others, because a containing set has to be strictly bigger than the set it contains, and in this family all sets have equal size. The value of k that makes this example have as many sets as possible is n/2 if n is even, or either of the nearest integers to n/2 if n is odd. For this choice, the number of sets in the family is ${\tbinom {n}{\lfloor n/2\rfloor }}$ .

Sperner's theorem states that these examples are the largest possible Sperner families over an n-element set. Formally, the theorem states that,

for every Sperner family S whose union has a total of n elements, $|S|\leq {\binom {n}{\lfloor n/2\rfloor }},$ and
equality holds if and only if S consists of all subsets of an n-element set that have size $\lfloor n/2\rfloor$ or all that have size $\lceil n/2\rceil$ .

Partial orders

Sperner's theorem can also be stated in terms of partial order width. The family of all subsets of an n-element set (its power set) can be partially ordered by set inclusion; in this partial order, two distinct elements are said to be incomparable when neither of them contains the other. The width of a partial order is the largest number of elements in an antichain, a set of pairwise incomparable elements. Translating this terminology into the language of sets, an antichain is just a Sperner family, and the width of the partial order is the maximum number of sets in a Sperner family. Thus, another way of stating Sperner's theorem is that the width of the inclusion order on a power set is ${\binom {n}{\lfloor n/2\rfloor }}$ .

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. In this terminology, Sperner's theorem states that the partially ordered set of all subsets of a finite set, partially ordered by set inclusion, has the Sperner property.

Proof

There are many proofs of Sperner's theorem, each leading to different generalizations (see Anderson (1987)).

The following proof is due to Lubell (1966). Let s_k denote the number of k-sets in S. For all 0 ≤ k ≤ n,

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

and, thus,

{s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leq {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 }}\leq \sum _{k=0}^{n}{s_{k} \over {n \choose k}}\leq 1,

which means

|S|=\sum _{k=0}^{n}s_{k}\leq {n \choose \lfloor {n/2}\rfloor }.

This completes the proof of part 1.

To have equality, all the inequalities in the preceding proof must be equalities. Since

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

if and only if $k=\lfloor {n/2}\rfloor$ or $\lceil {n/2}\rceil ,$ we conclude that equality implies that S consists only of sets of sizes $\lfloor {n/2}\rfloor$ or $\lceil {n/2}\rceil .$ For even n that concludes the proof of part 2.

For odd n there is more work to do, which we omit here because it is complicated. See Anderson (1987), pp. 3–4.

Generalizations

There are several generalizations of Sperner's theorem for subsets of ${\mathcal {P}}(E),$ the poset of all subsets of E.

No long chains

A chain is a subfamily $\{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)$ that is totally ordered, i.e., $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ (possibly after renumbering). The chain has r + 1 members and lengthr. An r-chain-free family (also called an r-family) is a family of subsets of E that contains no chain of length r. Erdős (1945) proved that the largest size of an r-chain-free family is the sum of the r largest binomial coefficients ${\binom {n}{i}}$ . The case r = 1 is Sperner's theorem.

p-compositions of a set

In the set ${\mathcal {P}}(E)^{p}$ of p-tuples of subsets of E, we say a p-tuple $(S_{1},\dots ,S_{p})$ is ≤ another one, $(T_{1},\dots ,T_{p}),$ if $S_{i}\subseteq T_{i}$ for each i = 1,2,...,p. We call $(S_{1},\dots ,S_{p})$ a p-composition ofE if the sets $S_{1},\dots ,S_{p}$ form a partition of E. Meshalkin (1963) proved that the maximum size of an antichain of p-compositions is the largest p-multinomial coefficient ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ that is, the coefficient in which all n_i are as nearly equal as possible (i.e., they differ by at most 1). Meshalkin proved this by proving a generalized LYM inequality.

The case p = 2 is Sperner's theorem, because then $S_{2}=E\setminus S_{1}$ and the assumptions reduce to the sets $S_{1}$ being a Sperner family.

No long chains in p-compositions of a set

Beck & Zaslavsky (2002) combined the Erdös and Meshalkin theorems by adapting Meshalkin's proof of his generalized LYM inequality. They showed that the largest size of a family of p-compositions such that the sets in the i-th position of the p-tuples, ignoring duplications, are r-chain-free, for every $i=1,2,\dots ,p-1$ (but not necessarily for i = p), is not greater than the sum of the $r^{p-1}$ largest p-multinomial coefficients.

Projective geometry analog

In the finite projective geometry PG(d, F_q) of dimension d over a finite field of order q, let ${\mathcal {L}}(p,F_{q})$ be the family of all subspaces. When partially ordered by set inclusion, this family is a lattice. Rota & Harper (1971) proved that the largest size of an antichain in ${\mathcal {L}}(p,F_{q})$ is the largest Gaussian coefficient ${\begin{bmatrix}d+1\\k\end{bmatrix}};$ this is the projective-geometry analog, or q-analog, of Sperner's theorem.

They further proved that the largest size of an r-chain-free family in ${\mathcal {L}}(p,F_{q})$ is the sum of the r largest Gaussian coefficients. Their proof is by a projective analog of the LYM inequality.

No long chains in p-compositions of a projective space

Beck & Zaslavsky (2003) obtained a Meshalkin-like generalization of the Rota–Harper theorem. In PG(d, F_q), a Meshalkin sequence of length p is a sequence $(A_{1},\ldots ,A_{p})$ of projective subspaces such that no proper subspace of PG(d, F_q) contains them all and their dimensions sum to $d-p+1$ . The theorem is that a family of Meshalkin sequences of length p in PG(d, F_q), such that the subspaces appearing in position i of the sequences contain no chain of length r for each $i=1,2,\dots ,p-1,$ is not more than the sum of the largest $r^{p-1}$ of the quantities

{\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}q^{s_{2}(n_{1},\ldots ,n_{p})},

where ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ (in which we assume that $d+1=n_{1}+\cdots +n_{p}$ ) denotes the p-Gaussian coefficient

{\begin{bmatrix}d+1\\n_{1}\end{bmatrix}}{\begin{bmatrix}d+1-n_{1}\\n_{2}\end{bmatrix}}\cdots {\begin{bmatrix}d+1-(n_{1}+\cdots +n_{p-1})\\n_{p}\end{bmatrix}}

and

s_{2}(n_{1},\ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+\cdots +n_{p-1}n_{p},

the second elementary symmetric function of the numbers $n_{1},n_{2},\dots ,n_{p}.$

Related Research Articles

In number theory, Waring's problem asks whether each natural number k has an associated positive integer s such that every natural number is the sum of at most s natural numbers raised to the power k. For example, every natural number is the sum of at most 4 squares, 9 cubes, or 19 fourth powers. Waring's problem was proposed in 1770 by Edward Waring, after whom it is named. Its affirmative answer, known as the Hilbert–Waring theorem, was provided by Hilbert in 1909. Waring's problem has its own Mathematics Subject Classification, 11P05, "Waring's problem and variants".

In mathematics, the floor function is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the least integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

In algebraic geometry, a projective variety is an algebraic variety that is a closed subvariety of a projective space. That is, it is the zero-locus in $of some finite family of homogeneous polynomials that generate a prime ideal, the defining ideal of the variety.$

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.

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 Bollobás (1965), Lubell (1966), Meshalkin (1963), and Yamamoto (1954). It is named for the initials of three of its discoverers. To include the initials of all four discoverers, it is sometimes referred to as the YBLM inequality.

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.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements. This number is called the width of the partial order. The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the graph's Laplacian matrix; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

In mathematics, the Gauss–Kuzmin–Wirsing operator is the transfer operator of the Gauss map that takes a positive number to the fractional part of its reciprocal. It is named after Carl Gauss, Rodion Kuzmin, and Eduard Wirsing. It occurs in the study of continued fractions; it is also related to the Riemann zeta function.

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.

In mathematics, Farkas' lemma is a solvability theorem for a finite system of linear inequalities. It was originally proven by the Hungarian mathematician Gyula Farkas. Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization. It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming. Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden-variable theory, given data from any specific set of measurements.

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proven by Euclid in his work Elements. There are several proofs of the theorem.

In mathematics, a Beatty sequence is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.

In mathematics, the Vitali covering lemma is a combinatorial and geometric result commonly used in measure theory of Euclidean spaces. This lemma is an intermediate step, of independent interest, in the proof of the Vitali covering theorem. The covering theorem is credited to the Italian mathematician Giuseppe Vitali. The theorem states that it is possible to cover, up to a Lebesgue-negligible set, a given subset E of R^d by a disjoint family extracted from a Vitali covering of E.

In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve. The terms path integral, curve integral, and curvilinear integral are also used; contour integral is used as well, although that is typically reserved for line integrals in the complex plane.

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897. The Dedekind number M(n) is the number of monotone Boolean functions of n variables. Equivalently, it is the number of antichains of subsets of an n-element set, the number of elements in a free distributive lattice with n generators, and one more than the number of abstract simplicial complexes on a set with n elements.

In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for Leon Mirsky and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.

The method of (hypergraph) containers is a powerful tool that can help characterize the typical structure and/or answer extremal questions about families of discrete objects with a prescribed set of local constraints. Such questions arise naturally in extremal graph theory, additive combinatorics, discrete geometry, coding theory, and Ramsey theory; they include some of the most classical problems in the associated fields.

In extremal set theory, the Ahlswede–Khachatrian theorem generalizes the Erdős–Ko–Rado theorem to $t$ -intersecting families. Given parameters $n$ , $k$ and $t$ , it describes the maximum size of a $t$ -intersecting family of subsets of $of size k, as well as the families achieving the maximum size.$

References

Anderson, Ian (1987), Combinatorics of Finite Sets, Oxford University Press.
Beck, Matthias; Zaslavsky, Thomas (2002), "A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains", Journal of Combinatorial Theory , Series A, 100 (1): 196–199, arXiv: math/0112068 , doi: 10.1006/jcta.2002.3295 , MR 1932078, S2CID 8136773 .
Beck, Matthias; Zaslavsky, Thomas (2003), "A Meshalkin theorem for projective geometries", Journal of Combinatorial Theory , Series A, 102 (2): 433–441, arXiv: math/0112069 , doi: 10.1016/S0097-3165(03)00049-9 , MR 1979545, S2CID 992137 .
Engel, Konrad (1997), Sperner theory, Encyclopedia of Mathematics and its Applications, vol. 65, Cambridge: Cambridge University Press, p. x+417, doi:10.1017/CBO9780511574719, ISBN 0-521-45206-6, MR 1429390 .
Engel, K. (2001) [1994], "Sperner theorem", Encyclopedia of Mathematics , EMS Press
Erdős, P. (1945), "On a lemma of Littlewood and Offord" (PDF), Bulletin of the American Mathematical Society , 51 (12): 898–902, doi: 10.1090/S0002-9904-1945-08454-7 , MR 0014608
Lubell, D. (1966), "A short proof of Sperner's lemma", Journal of Combinatorial Theory , 1 (2): 299, doi: 10.1016/S0021-9800(66)80035-2 , MR 0194348 .
Meshalkin, L.D. (1963), "Generalization of Sperner's theorem on the number of subsets of a finite set", Theory of Probability and Its Applications (in Russian), 8 (2): 203–204, doi:10.1137/1108023 .
Rota, Gian-Carlo; Harper, L. H. (1971), "Matching theory, an introduction", Advances in Probability and Related Topics, Vol. 1, New York: Dekker, pp. 169–215, MR 0282855 .
Sperner, Emanuel (1928), "Ein Satz über Untermengen einer endlichen Menge", Mathematische Zeitschrift (in German), 27 (1): 544–548, doi:10.1007/BF01171114, hdl: 10338.dmlcz/127405 , JFM 54.0090.06, S2CID 123451223 .

External links

Sperner's Theorem at cut-the-knot
Sperner's theorem on the polymath1 wiki

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.