Fact-checked by Grok 2 weeks ago

Sperner's theorem

Sperner's theorem is a cornerstone of extremal set theory, stating that in the Boolean lattice B_n, which consists of the power set of an n-element set ordered by inclusion, the maximum size of an antichain—a collection of subsets where no one contains another—is given by the central binomial coefficient \binom{n}{\lfloor n/2 \rfloor}, achieved precisely by the family of all subsets of size \lfloor n/2 \rfloor.^[1]^[2] This result, proved by Emanuel Sperner in 1928, establishes that the Boolean lattice is Sperner, meaning its largest antichain coincides with the size of its largest rank level.^[3] The theorem's proof relies on the structure of the Boolean lattice as a ranked, symmetric, and unimodal poset, often demonstrated via the LYM inequality (named after Lubell, Yamamoto, and Meshalkin) or symmetric chain decompositions.^[4] Sperner's original 1928 paper, titled "Ein Satz über Untermengen einer endlichen Menge" (published in Mathematische Zeitschrift), provided an elegant combinatorial argument that simplified earlier results by Macaulay on graded ideals.^[2] Subsequent developments, such as de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk's 1951 symmetric chain decomposition, offered alternative proofs and extended the theorem's implications to other product posets.^[4] Beyond its foundational role, Sperner's theorem has profound applications in combinatorics and related fields. In extremal set theory, it bounds the size of intersecting families and inspires generalizations like the Erdős–Ko–Rado theorem for uniform intersecting sets.^[5] It also underpins results in coding theory, where antichains correspond to constant-weight codes without containment, and in statistical mechanics for modeling partition functions over subsets.^[2] The theorem's Sperner property has been generalized to k-Sperner posets, where the union of k largest ranks bounds the size of k-chains of antichains, with the Boolean lattice being strongly Sperner for all k as shown by Erdős in 1945.^[2]

Introduction

Statement

Sperner's theorem addresses the structure of the power set of an n-element set, which consists of all $2^n subsets ordered by inclusion. An antichain, also known as a Sperner family, is a collection of these subsets such that no subset properly contains another. The theorem states that in this partially ordered set (poset), the largest possible antichain has size \binom{n}{\lfloor n/2 \rfloor}, and this maximum is achieved by taking all subsets of size \lfloor n/2 \rfloor (or, equivalently for even n, all subsets of size n/2 or n/2 + 1, though the middle level is unique in size). This result characterizes the width of the Boolean lattice \mathcal{B}_n, the poset formed by the power set under inclusion, as equal to the largest binomial coefficient \binom{n}{k} where k = \lfloor n/2 \rfloor. For example, when n=3, the power set has 8 elements, and the largest antichain consists of the three 1-element subsets (or the three 2-element subsets), with size \binom{3}{1} = 3.

History

Sperner's theorem emerged within the broader development of order theory and combinatorics in the early 20th century, building on foundational ideas in partial orders introduced by Richard Dedekind in the 1890s, particularly his studies of monotone functions and lattice structures. The theorem itself was established by Emanuel Sperner in his 1928 paper "Ein Satz über Untermengen einer endlichen Menge," published in Mathematische Zeitschrift, where he proved that the largest antichain in the power set of an n-element set is given by the collection of all subsets of size \lfloor n/2 \rfloor. Sperner, then a research student at the University of Hamburg, submitted the paper in February 1927, motivated by problems in set theory and partially ordered sets.^[6] The result is named after Sperner, reflecting his original proof for the Boolean lattice, although independent proofs have appeared in later works, including one by Donald Knuth in The Art of Computer Programming, Volume 4A (2011).^[7] By the 1940s, the theorem had gained recognition as a cornerstone of combinatorics, influencing extremal set theory through extensions such as Paul Erdős's 1945 generalization to the maximum size of families without k-chains, which equals the sum of the k largest binomial coefficients.^[8]

Mathematical Background

Partial Orders and Antichains

A partial order on a set P is a binary relation \leq that is reflexive (x \leq x for all x \in P), antisymmetric (if x \leq y and y \leq x, then x = y), and transitive (if x \leq y and y \leq z, then x \leq z).^[9] The pair (P, \leq) is called a partially ordered set, or poset.^[9] In a poset, a chain is a subset in which every pair of elements is comparable, meaning for any two distinct elements x, y in the subset, either x \leq y or y \leq x.^[9] An antichain, by contrast, is a subset in which no two distinct elements are comparable.^[9] The width of a poset is the cardinality of its largest antichain.^[9] By Dilworth's theorem, this equals the minimum number of chains needed to partition the poset.^[10] The dual statement equates the minimum number of antichains in a partition to the size of the largest chain.^[9] A graded poset is one equipped with a rank function that assigns to each element a non-negative integer rank such that the rank increases by exactly one along any cover relation (where x covers y if y < x and no z satisfies y < z < x), and all maximal chains have the same length.^[11] Elements of the same rank form a level or rank P_i. A graded poset has the Sperner property if its largest antichain is one of these ranks (i.e., the maximum antichain size equals the size of the largest rank).^[11] A classic example is the power set of an n-element set, ordered by inclusion (\subseteq), which forms a poset where A \subseteq B if every element of A is in B.^[12] This poset is graded, with the rank of a subset equal to its cardinality, so ranks correspond to subsets of fixed size k for k = 0 to n.^[12]

The Boolean Lattice

The Boolean lattice, often denoted B_n or $2^{}, is the power set of the finite set = \{1, 2, \dots, n\}, equipped with the partial order of set inclusion, where A \leq B if and only if A \subseteq B.^[13] This structure forms a graded poset of rank n, with the rank function given by the cardinality of each subset, so the minimal element is the empty set at rank 0 and the maximal element is the full set $$ at rank n. The ranks, or levels, of the Boolean lattice are the collections of subsets of fixed size: the k-th level consists of all k-element subsets of $$, and its size is the binomial coefficient \binom{n}{k}, which counts the number of ways to choose k elements from n.^[14] The sequence of level sizes \binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n} is unimodal, meaning it increases up to a peak and then decreases symmetrically; specifically, for even n, the maximum occurs at k = n/2, while for odd n, the two central values at k = (n-1)/2 and k = (n+1)/2 are equal and maximal.^[15] As a lattice, the Boolean lattice is distributive, with the meet operation corresponding to set intersection and the join to set union; it is in fact a Boolean algebra, the free distributive lattice on n generators. A key structural property is its symmetric chain decomposition, which partitions the entire poset into disjoint saturated chains that are symmetric with respect to the ranks, meaning each chain is invariant under complementation (replacing subsets with their complements in $$); this decomposition was constructed by de Bruijn, Tengbergen, and Kruyswijk in 1951.^[16] The covering relations in the poset are the pairs where one subset is obtained from another by adding or removing a single element, connecting consecutive rank levels. The Hasse diagram of the Boolean lattice visualizes these covering relations as edges between elements differing by one element. For n=1, it is a chain of two elements: \emptyset below \{1\}. For n=2, with

{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}}=\{1,2\}

, the diagram has \emptyset at the bottom, connected to the singletons \{1\} and \{2\} in the middle level, both of which connect upward to the full set \{1,2\} at the top, forming a diamond shape. For n=3, the structure expands to a central level of three doubletons \{1,2\}, \{1,3\}, \{2,3\}, with appropriate connections from the three singletons below and to the full set above, remaining a layered graph for small n.^[13]

Proofs

Sperner's Original Proof

Sperner's original proof from 1928 uses a combinatorial argument based on Hall's marriage theorem. Consider the Boolean lattice B_n as a ranked poset with ranks corresponding to subset sizes. For an antichain \mathcal{F}, construct bipartite graphs between consecutive ranks R_k and R_{k+1}, where edges represent inclusion. By applying Hall's theorem, one can show that there exists a matching that injects \mathcal{F} into the middle rank \lfloor n/2 \rfloor, implying |\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor}. Equality holds for the full middle level. This approach simplifies earlier algebraic results by Macaulay on the dimension of graded ideals.^[3]^[17]

Double-Counting Argument

One standard proof of Sperner's theorem employs a double-counting argument on the maximal chains in the Boolean lattice B_n, which consists of the power set of an n-element set ordered by inclusion.^[18] The total number of maximal chains in B_n, each connecting the empty set to the full set by successively adding one element at a time, is exactly n!, as each such chain corresponds to a permutation of the n elements.^[18] Consider an antichain \mathcal{F} in B_n. Since no two sets in \mathcal{F} are comparable, each maximal chain intersects \mathcal{F} in at most one set. Thus, the number of pairs (C, A) where C is a maximal chain and A \in \mathcal{F} with A \subset C is at most the total number of maximal chains, which is n!. On the other hand, for a fixed A \in \mathcal{F} with |A| = k, the number of maximal chains containing A is k! \cdot (n - k)!, as there are k! ways to order the elements already in A and (n - k)! ways to order the additions of the remaining elements.^[18] Therefore, summing over all A \in \mathcal{F}, we obtain

\sum_{A \in \mathcal{F}} k! \cdot (n - k)! \leq n!,

where k = |A|. Dividing both sides by n! yields

\sum_{A \in \mathcal{F}} \frac{1}{\binom{n}{k}} \leq 1.

Let \mathcal{F}_k = \{ A \in \mathcal{F} : |A| = k \}, so |\mathcal{F}| = \sum_{k=0}^n |\mathcal{F}_k|. The inequality then becomes

\sum_{k=0}^n \frac{|\mathcal{F}_k|}{\binom{n}{k}} \leq 1.

Multiplying through by \binom{n}{m} for any fixed m gives

\sum_{k=0}^n |\mathcal{F}_k| \cdot \frac{\binom{n}{m}}{\binom{n}{k}} \leq \binom{n}{m}.

In particular, choosing m to maximize \binom{n}{m} (typically near n/2) and noting that \frac{\binom{n}{m}}{\binom{n}{k}} \geq 1 for all k when m is the mode, we bound |\mathcal{F}| \leq \max_k \binom{n}{k}, with equality if and only if \mathcal{F} is contained in the largest level(s).^[18] This argument, which establishes the LYM inequality and is due to Lubell (1966), demonstrates the theorem via elementary counting.

Proof Using the LYM Inequality

The Lubell–Yamamoto–Meshalkin (LYM) inequality provides a powerful tool for proving Sperner's theorem by establishing a bound on the weighted size of an antichain in the power set of an n-element set. For an antichain \mathcal{A} in the Boolean lattice $2^{}, the LYM inequality asserts that

\sum_{A \in \mathcal{A}} \frac{1}{\binom{n}{|A|}} \leq 1.

^[19] This inequality was independently discovered by David Lubell in 1966, Koichi Yamamoto in 1954, and Lev Meshalkin in 1963.^[20]^[19] To derive Sperner's theorem from the LYM inequality, observe that the binomial coefficients \binom{n}{k} achieve their maximum at k = \lfloor n/2 \rfloor, so \binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor} for all k, which implies \frac{1}{\binom{n}{k}} \geq \frac{1}{\binom{n}{\lfloor n/2 \rfloor}}. Substituting into the LYM sum yields

\sum_{A \in \mathcal{A}} \frac{1}{\binom{n}{|A|}} \geq \frac{|\mathcal{A}|}{\binom{n}{\lfloor n/2 \rfloor}} \leq 1,

so |\mathcal{A}| \leq \binom{n}{\lfloor n/2 \rfloor}, with equality when \mathcal{A} consists of all subsets of size \lfloor n/2 \rfloor.^[19] A standard proof of the LYM inequality proceeds by double-counting the pairs (C, A) where C is a maximal chain from \emptyset to

and $A \in \mathcal{A} \cap C$. There are exactly $n!$ such maximal chains, since each corresponds to a [permutation](/page/Permutation) of

ordering the additions of elements. For a fixed A \in \mathcal{A} with |A| = k, the number of maximal chains containing A is k! (n-k)!, as the first k steps fill A in any order and the remaining n-k steps fill the complement. Thus, the total number of pairs is \sum_{A \in \mathcal{A}} k! (n-k)! \leq n!, and dividing by n! gives

\sum_{A \in \mathcal{A}} \frac{1}{\binom{n}{k}} \leq 1,

since \binom{n}{k} = \frac{n!}{k! (n-k)!}. The antichain property ensures no chain intersects \mathcal{A} more than once, so the bound holds without overcounting.^[21] The LYM inequality is stronger than Sperner's theorem because it not only bounds the size of antichains but also controls their distribution across levels of the Boolean lattice, enabling applications beyond Sperner such as normalized matching theorems and extensions in extremal set theory.^[19]

Applications

In Extremal Set Theory

Sperner's theorem establishes the maximum size of an antichain in the power set of an n-element set as the binomial coefficient \binom{n}{\lfloor n/2 \rfloor}, which serves as a fundamental bound in extremal set theory for various problems involving set families without containment relations. In the context of the Erdős–Ko–Rado theorem, this bound directly applies to uniform intersecting families, as a k-uniform intersecting family forms an antichain in the Boolean lattice (since distinct sets of equal cardinality cannot contain one another). Thus, the size of any k-uniform intersecting family is at most \binom{n}{k}, with equality possible only for the full level when no intersecting condition is imposed; the Erdős–Ko–Rado theorem tightens this to \binom{n-1}{k-1} for n \geq 2k, highlighting Sperner's role as the baseline upper limit for uniform antichains underlying intersecting structures. The theorem also connects to the union-closed sets conjecture, proposed by Péter Frankl in 1979, which asserts that every finite nonempty union-closed family of subsets of an n-element set contains an element belonging to at least half of the sets in the family. Links between Sperner's theorem and the conjecture emerge through the analysis of antichain sizes within union-generated families, where the maximal elements of a union-closed family form an antichain, and Sperner's capacity bounds the potential scale of these structures in the Boolean lattice. Averaging techniques, drawing on probabilistic interpretations akin to random antichains in Sperner's theorem, have been employed to derive partial results, such as guarantees for large union-closed families where element frequencies approach the conjectured threshold via antichain distribution properties. In coding theory, Sperner's theorem determines the maximum cardinality of a constant-weight code whose supports form an antichain under inclusion, corresponding to a collection of equal-sized subsets with no containment (trivially satisfied for distinct sets of fixed weight w). The extremal size is \binom{n}{w}, achieved by the full w-uniform family, providing the theoretical limit for error-correcting codes like superimposed codes where support inclusions are forbidden to ensure detectability. This bound influences the design of constant-weight binary codes with minimum Hamming distance constraints, as the antichain property ensures robustness against certain error patterns without nested supports. Algorithmically, Sperner's theorem guides the computation of maximum antichains in the Boolean lattice, where dynamic programming efficiently calculates the sizes of all uniform levels via the recurrence for binomial coefficients, \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, identifying the middle level as the largest with size \binom{n}{\lfloor n/2 \rfloor}. This approach confirms the theorem's bound in polynomial time relative to n, serving as a building block for larger extremal computations or simulations in set systems. As an example in hypergraph Turán problems, Sperner's theorem limits the size of independent sets by bounding the largest antichain in the underlying set system, which corresponds to the maximum collection of vertices avoiding forbidden subhypergraphs interpreted as containments. In k-uniform hypergraphs, this provides an upper bound on the independence number, as the largest set without a full edge aligns with antichain constraints in the Boolean structure, informing extremal densities for Turán numbers \mathrm{ex}(n, \mathcal{F}) where \mathcal{F} involves containment-free families.^[22]

Connections to Other Theorems

Sperner's theorem determines the width of the Boolean lattice B_n, defined as the cardinality of the largest antichain, which is \binom{n}{\lfloor n/2 \rfloor}. By Dilworth's theorem, this width equals the minimum number of chains required to partition the poset; thus, B_n admits a chain partition into exactly \binom{n}{\lfloor n/2 \rfloor} chains. The dual result, Mirsky's theorem, states that the height of a poset (size of the largest chain) equals the minimum number of antichains needed for a partition. In B_n, the height is n+1, so the lattice partitions into n+1 antichains, corresponding to its rank levels. A key proof technique for Sperner's theorem involves the LYM inequality, which bounds the relative size of shadows of set families. This inequality follows from Harper's vertex-isoperimetric theorem of the 1960s, which characterizes the subsets of the hypercube minimizing the size of their t-neighborhoods as initial segments in the lexicographic order, thereby implying bounds on partial shadows that yield Sperner's result. Recent developments connect Sperner's theorem to approximation algorithms, particularly through randomized rounding techniques for optimizing over Sperner families. For instance, in fair division problems modeled as hypergraph labelings, linear programming relaxations with Sperner constraints are solved and rounded to integral solutions preserving approximation guarantees.^[23]

Generalizations

Versions Without Long Chains

A significant generalization of Sperner's theorem, due to Paul Erdős, determines the maximum size of a family of subsets of an n-element set that contains no chain of r+1 comparable sets, for r ≥ 1. Such families are known as r-Sperner families, with the case r=1 recovering the original Sperner theorem on antichains. Erdős proved that the size of the largest r-Sperner family is the sum of the r largest binomial coefficients \binom{n}{k}.^[8] Equality holds if and only if the family consists of all subsets from the r largest levels of the Boolean lattice, which, due to the unimodality of the binomial coefficients, are r consecutive levels centered around k ≈ n/2. For example, when n is even and r=2, the optimal family includes all subsets of sizes n/2 and n/2 + 1.^[8] One approach to proving Erdős's theorem involves truncating the Boolean lattice to any r consecutive ranks, forming a subposet of height r where the longest possible chain has r elements. Within this truncated poset, Sperner's theorem implies that the largest antichain has size equal to the largest level in the truncation. Since any r-Sperner family in the full lattice intersects each maximal chain in at most r levels, its size cannot exceed the maximum over all such truncations, which is achieved by the r middle levels.^[8]

Extensions to p-Compositions

A generalization of Sperner's theorem extends to the poset of p-compositions of an n-element set, defined as the set of all functions from = \{1, 2, \dots, n\} to = \{1, 2, \dots, p\}, ordered pointwise: f \leq g if f(i) \leq g(i) for all i \in . This poset, isomorphic to the product of n chains each of length p, has cardinality p^n. In 1963, L. D. Meshalkin proved that the size of the largest antichain in this poset is the maximum multinomial coefficient \max \binom{n}{k_1, \dots, k_p}, where the maximum is taken over all non-negative integers k_1, \dots, k_p summing to n. This bound is tight and achieved by taking all functions whose preimage sizes |f^{-1}(j)| = k_j for j = 1, \dots, p correspond to the maximizing composition, which occurs when the k_j are as equal as possible (each roughly n/p). For p=2, this recovers the original Sperner's theorem on the Boolean lattice. An LYM-type inequality holds for antichains in this poset: if \mathcal{A} is an antichain, then \sum_{f \in \mathcal{A}} \frac{1}{\binom{n}{|f^{-1}(1)|, \dots, |f^{-1}(p)|}} \leq 1.^[24] This inequality implies Meshalkin's bound and has applications to multisets and colored set families, where elements are partitioned into p labeled classes.^[24]

Analogs in Projective Geometry

In the context of projective geometry over finite fields, analogs of Sperner's theorem arise in the study of the subspace lattice L_q(n), which consists of all subspaces of the n-dimensional vector space \mathbb{F}_q^n over the finite field \mathbb{F}_q, ordered by inclusion and graded by dimension from 0 to n.^[25] This lattice forms a ranked poset where the rank function is the dimension of the subspace, and antichains correspond to collections of incomparable subspaces (no one contains another). The q-analog of Sperner's theorem, established by Harper and Rota, states that the largest antichain in L_q(n) is the collection of all subspaces of dimension k = \lfloor n/2 \rfloor, with cardinality given by the Gaussian binomial coefficient \dbinom{n}{k}_q = \prod_{i=0}^{k-1} \frac{q^{n-i} - 1}{q^{k-i} - 1}.^[26] The proof relies on a q-analog of the LYM inequality, also due to Harper and Rota, which bounds the "shadow" of antichains in terms of normalized sizes relative to the Gaussian coefficients; for t=1, this implies the Sperner property by showing that no antichain can exceed the middle level.^[25] A further generalization addresses families avoiding long chains: any antichain in L_q(n) containing no t+1-chain (a sequence of t+1 subspaces where each properly contains the previous) has size at most the sum of the t largest Gaussian binomial coefficients \sum_{i=1}^t \dbinom{n}{k_i}_q, where k_1, \dots, k_t are the dimensions yielding the maximum values.^[25] These results find applications in coding theory, particularly for constant-dimension subspace codes, where an antichain of subspaces of fixed dimension serves as a code with minimum subspace distance determined by non-inclusion; the q-Sperner capacity bounds the maximum code size, aiding in the construction of error-correcting codes for network coding over finite fields.^[27]

References

[1]
Sperner's Theorem -- from Wolfram MathWorld
The maximum cardinal number of a collection of subsets of a t-element set T, none of which contains another, is the binomial coefficient (t; |_t/2_|), ...
[2]
[PDF] Sperner's Theorem 1 2. Normalized Flow and the - UChicago Math
Aug 31, 2019 · In this paper, we give an overview on investigations into the. Sperner property of posets and particularly the posets induced by applying.
[3]
[PDF] Sperner's Theorem 1 2. Normalized Flow and the
Aug 31, 2019 · In this paper, we give an overview on investigations into the. Sperner property of posets and particularly the posets induced by applying.
[4]
[PDF] 18.212 S19 Algebraic Combinatorics, Lecture 17: Sperner's property ...
Mar 15, 2019 · Theorem 1 (Sperner's theorem (1928)). The Boolean lattice Bn is Sperner. ... The middle rank is the maximal rank number, and any antichain cannot ...
[5]
[PDF] Sperner's Theorem and a Problem of Erdős, Katona and Kleitman
Sperner's theorem is a central result in extremal set theory, giving the size of the largest family of sets not containing a 2-chain, F1 ⊂ F2. Erd˝os later ...<|control11|><|separator|>
[6]
Emanuel Sperner (1905 - 1980) - Biography - MacTutor
The aim of this paper was to produce a simpler and shorter proof of a combinatorial theorem proved by F S Macaulay in 1927. The author also added new versions ...
[7]
The Art of Computer Programming (TAOCP) - CS Stanford
This earlier collection includes Volumes 1, 2, 3, and 4A; Volume 1; and Volume 4 Fascicles 5 and 6. eBook versions. These volumes are now available also in ...Missing: Sperner's | Show results with:Sperner's
[8]
[PDF] Problems and Results in combinatorial analysis
A well known theorem of Sperner [57] states that if Aia S, 15i5m, is such that no A, contains any other, then max m=(aA). The theorem of Sperner has many appli-.Missing: post- | Show results with:post-<|control11|><|separator|>
[9]
[PDF] Chains and Antichains
Chains and Antichains Page 2 Basic definitions finite partially ordered set (poset) P: a set P with a binary operation ≤ satisfying t ≤ t for all t ∈ P ( ...
[10]
[PDF] A Decomposition Theorem for Partially Ordered Sets - UCSD Math
This paper will be devoted to the proof of the following theorem and some of its applications. THEOREM 1.1. Let every set of k + 1 elements of a partially ...
[11]
[PDF] 4 The Sperner property.
In this section we consider a surprising application of certain adjacency ma trices to some problems in extremal set theory. An important role will also.
[12]
Model selection over partially ordered sets - PNAS
... set inclusion, the least element is given by the empty set, and the rank of a subset is its cardinality. This poset is called the Boolean poset (14).
[13]
[PDF] combinatorial aspects of partially ordered sets
This section will introduce the concept of a graded poset and a few associated results. 2.1. Rank Functions. Definition 2.1.1. A rank function of a poset P is ...Missing: size | Show results with:size
[14]
Binomial Coefficients - Discrete Mathematics - An Open Introduction
(nk)=|Bnk|, ( n k ) = | B k n | , the number of n n -bit strings of weight k. · (nk) ( n k ) is the number of subsets of a set of size n n each with cardinality ...
[15]
[PDF] Enumerative Combinatorics 4: Unimodality
So, if n is even, the binomial coefficients increase up to k = n/2 and then decrease; if n is odd, the two middle values (k = (n−1)/2 and k = (n+ 1)/2) are ...
[16]
[1303.4336] Supersaturation in the Boolean lattice - arXiv
Mar 18, 2013 · We prove a "supersaturation-type" extension of both Sperner's Theorem (1928) and its generalization by Erdos (1945) to k-chains.
[17]
[PDF] A Short Proof of Sperner's Lemma
Let S denote a set of N objects. By a Sperner collection on S we mean a collection of subsets of S such that no one contain another. In [1],.
[18]
https://sites.math.rutgers.edu/~zeilberg/akherim/lubell1966.pdf
[19]
https://doi.org/10.1016/S0021-9800(66)80035-2
[20]
https://doi.org/10.2969/jmsj/00630343
[21]
[PDF] EXTREMAL SET THEORY 1 Sperner's theorem
The Erd˝os-Rado investigations of ∆-systems constitute a part of extremal set theory, which concerns extremal sizes of set families with prescribed ...
[22]
[PDF] Sperner's Colorings, Hypergraph Labeling Problems and Fair Division
This algorithm solves the. LE-Rel relaxation and then rounds the fractional solu- tion to an integral one, using the randomized rounding technique of Kleinberg ...
[23]
on a lemma of littlewood and offord
ON A LEMMA OF LITTLEWOOD AND OFFORD. P. ERDÖS. Recently Littlewood and Offord1 proved the following lemma: Let be complex numbers with \xi\ ^ 1 . Consider the.
[24]
[math/0112067] A unifying generalization of Sperner's theorem - arXiv
Dec 7, 2001 · We unify Erdos's, Meshalkin's, and Griggs-Stahl-Trotter's inequalities with a common generalization. We similarly unify their accompanying LYM ...Missing: 1945 | Show results with:1945<|separator|>
[25]
[PDF] Very Generalized LYM Inequality - arXiv
Sep 25, 2025 · subspace lattice Lq(n), Rota and Harper established the q-analog of the LYM inequality as follows: Rota-Harper Theorem [12]. Any t-chain ...<|control11|><|separator|>
[26]
[PDF] Chapter 2. Matching theory. 2.1. What is matching theory?
Rota: 'Roughly speaking, matching theory is concerned with the possibility and the number of ways of covering a large, irregularly shaped combinatorial object ...
[27]
Submodule codes as spherical codes in buildings
Mar 23, 2023 · We give a generalization of subspace codes by means of codes of modules over finite com- mutative chain rings. We define a new class of Sperner ...