Chapter 18: Extremal Set Theory

Which layer of the Boolean lattice gives the largest antichain?

Imagine that each subset of four features describes a possible software configuration or system state. We want to construct a collection of configurations in which no configuration contains another: every chosen configuration possesses a unique combination of features that prevents it from being a subset of any other chosen configuration. How many such configurations can we maintain simultaneously?

Write $[n]=\{1,2,\ldots,n\}$. The Boolean lattice $2^{[n]}$ is the collection of all $2^n$ subsets of $[n]$, ordered by set inclusion $\subseteq$. Its rank-$k$ layer, written $\binom{[n]}{k}$, consists of all $k$-element subsets and has size $\binom{n}{k}$. A set family $\mathcal{F}$ is a collection of distinct subsets; an antichain (or Sperner family) is a family in which no two distinct members are comparable by inclusion (for all $A, B \in \mathcal{F}$ with $A \ne B$, $A \not\subseteq B$).

Every single layer $\binom{[n]}{k}$ is automatically an antichain because two distinct sets of equal size can never contain one another. The ratio of consecutive layer sizes:

$$ \frac{\binom{n}{k+1}}{\binom{n}{k}}=\frac{n-k}{k+1} $$

shows that layer sizes strictly increase up to $k = \lfloor n/2 \rfloor$ and then decrease. Thus, the single largest layer is the middle layer $\binom{[n]}{\lfloor n/2 \rfloor}$. This answers which single layer is largest. The central question of extremal set theory is whether mixing subsets from multiple layers can produce an antichain larger than the middle layer. Sperner's theorem proves that it cannot.

18.1 Sperner's theorem and LYM inequality

What & Concept. Counting maximal chains provides a powerful probabilistic framework for measuring set family sizes. In $2^{[n]}$, a maximal chain is a sequence of $n+1$ nested subsets $\varnothing = C_0 \subset C_1 \subset C_2 \subset \cdots \subset C_n = [n]$, where $|C_k|=k$. There are exactly $n!$ maximal chains, each corresponding to a unique permutation $\pi$ of $[n]$.

A single set $A \subseteq [n]$ of size $k$ lies on exactly $k!(n-k)!$ maximal chains (the elements of $A$ must appear in the first $k$ positions of the permutation, and the remaining $n-k$ elements in the last $n-k$ positions). Therefore, choosing $A$ consumes a fraction $k!(n-k)! / n! = 1/\binom{n}{k}$ of all available maximal chains in the Boolean lattice.

Definition (Lubell Mass & LYM Inequality). For any antichain $\mathcal{F} \subseteq 2^{[n]}$, its Lubell mass $L(\mathcal{F})$ is the sum of chain consumption fractions:

$$ L(\mathcal F):=\sum_{A\in\mathcal F}\frac{1}{\binom{n}{|A|}}\le1. $$

The inequality holds because an antichain can contain at most one element from any single maximal chain. Summing indicator variables over all $n!$ maximal chains proves that the total consumed chain capacity cannot exceed $100\%$.

Sperner's Theorem (1927). Let $M = \binom{n}{\lfloor n/2 \rfloor}$ be the maximum layer size in $2^{[n]}$. For any antichain $\mathcal{F} \subseteq 2^{[n]}$:

$$ |\mathcal F|\le \binom{n}{\lfloor n/2\rfloor}. $$

Proof via LYM: Since $\binom{n}{|A|} \le M$ for every subset $A$, we have $\frac{1}{M} \le \frac{1}{\binom{n}{|A|}}$. Substituting into LYM gives:

$$ \frac{|\mathcal{F}|}{M} = \sum_{A \in \mathcal{F}} \frac{1}{M} \le \sum_{A \in \mathcal{F}} \frac{1}{\binom{n}{|A|}} \le 1 \implies |\mathcal{F}| \le M. $$

Solved Example. For the four-member mixed antichain $\mathcal{F} = \{\{1\}, \{2,3\}, \{2,4\}, \{3,4\}\}$ on $[4]$, its Lubell mass is:

$$ L(\mathcal F)=\frac{1}{\binom{4}{1}} + 3 \cdot \frac{1}{\binom{4}{2}} = \frac{1}{4} + \frac{3}{6} = \frac{3}{4} \le 1. $$

Exercise. An antichain on $[6]$ contains four 2-sets and ten 3-sets. How many 4-sets can it contain? Hint: Binomial weights are $\binom{6}{2}=15, \binom{6}{3}=20, \binom{6}{4}=15$. Solution: Let $x$ be the number of 4-sets. LYM requires $\frac{4}{15} + \frac{10}{20} + \frac{x}{15} \le 1 \implies \frac{4+x}{15} \le \frac{1}{2} \implies 4+x \le 7.5 \implies x \le 3$.

18.2 Erdős–Ko–Rado theorem

What & Definitions. A set family $\mathcal{F}$ is $k$-uniform if every member has size $k$ ($\mathcal{F} \subseteq \binom{[n]}{k}$). A family is intersecting if $A \cap B \ne \varnothing$ for all $A, B \in \mathcal{F}$.

A natural intersecting family is a star family: choose a fixed center element $x \in [n]$ and include all $k$-element sets containing $x$. The size of a star family is $\binom{n-1}{k-1}$ (choosing $k-1$ remaining elements from $[n] \setminus \{x\}$).

Erdős–Ko–Rado Theorem (1961). For integers $n \ge 2k$, if $\mathcal{F} \subseteq \binom{[n]}{k}$ is an intersecting $k$-uniform family, then:

$$ |\mathcal F|\le\binom{n-1}{k-1}. $$

When $n > 2k$, equality holds if and only if $\mathcal{F}$ is a star family. When $n = 2k$, other non-star extremal families exist (such as pairing each $k$-set with its complement $[2k] \setminus A$ and choosing one from each pair).

Why $n \ge 2k$ is Required: If $n < 2k$, any two $k$-subsets must overlap by the Pigeonhole Principle ($k + k = 2k > n$). In that regime, the entire layer $\binom{[n]}{k}$ is intersecting, yielding size $\binom{n}{k} > \binom{n-1}{k-1}$.

18.3 Intersecting and cross-intersecting set families

What & Definitions. Two set families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting if $A \cap B \ne \varnothing$ for every $A \in \mathcal{A}$ and every $B \in \mathcal{B}$. Crucially, members within $\mathcal{A}$ (or within $\mathcal{B}$) are not required to intersect each other.

Solved Example. On $[4]$, let $\mathcal{A} = \{12, 34\}$ and $\mathcal{B} = \{13, 24\}$. Within $\mathcal{A}$, $12 \cap 34 = \varnothing$. Within $\mathcal{B}$, $13 \cap 24 = \varnothing$. However, the two families are cross-intersecting because all four cross-intersections are nonempty:

Boundary-Case Sum Bound. If $\mathcal{A}, \mathcal{B} \subseteq \binom{[2k]}{k}$ are cross-intersecting $k$-uniform families on ground set $[2k]$, then for any $A \in \mathcal{A}$, its complement $A^c = [2k] \setminus A$ cannot belong to $\mathcal{B}$. Since complementation is a bijection on $\binom{[2k]}{k}$:

$$ |\mathcal A|+|\mathcal B|\le\binom{2k}{k}. $$

Exercise. Replace $\mathcal{B}$ in the matrix above with $\{13, 24, 12\}$. Is the pair $(\mathcal{A}, \mathcal{B})$ still cross-intersecting? Hint: Inspect row $34 \in \mathcal{A}$ and column $12 \in \mathcal{B}$. Solution: No, because $34 \cap 12 = \varnothing$. A single empty entry invalidates cross-intersectingness.

18.4 Kruskal–Katona theorem

What & Definitions. The lower shadow of a $k$-uniform family $\mathcal{F} \subseteq \binom{[n]}{k}$ is the collection of all $(k-1)$-element subsets contained in at least one member of $\mathcal{F}$:

$$ \partial\mathcal F=\{B \in \tbinom{[n]}{k-1} : B\subset A\text{ for some }A\in\mathcal F\}. $$

For a family of 3-element sets (triples), its shadow consists of all 2-element pairs that appear in those triples. The Kruskal–Katona theorem answers: What is the minimum possible size of $\partial \mathcal{F}$ for a family of size $|\mathcal{F}| = m$?

Colexicographic (Colex) Order. For equal-sized sets $A, B$, we say $A <_{\mathrm{colex}} B$ if the maximum element in their symmetric difference $A \mathbin{\triangle} B$ belongs to $B$. The initial 3-sets in colex order are:

$$ 123 <_{\mathrm{colex}} 124 <_{\mathrm{colex}} 134 <_{\mathrm{colex}} 234 <_{\mathrm{colex}} 125 <_{\mathrm{colex}} 135 <_{\mathrm{colex}} 235 \dots $$

Colex order minimizes shadow size because it packs sets into the smallest possible ground set $\{1, 2, \ldots, a_k\}$ before introducing a new element $a_k + 1$.

Kruskal–Katona Theorem (1963 / 1968). Every integer $m \ge 1$ has a unique $k$-binomial expansion:

$$ m=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\cdots+\binom{a_s}{s}, \qquad a_k > a_{k-1} > \cdots > a_s \ge s \ge 1. $$

For any $k$-uniform family $\mathcal{F}$ of size $|\mathcal{F}|=m$, its lower shadow satisfies:

$$ |\partial\mathcal F|\ge \binom{a_k}{k-1}+\binom{a_{k-1}}{k-2}+\cdots+\binom{a_s}{s-1}. $$

The lower bound is attained by taking the first $m$ $k$-element sets in colexicographic order.

Solved Example. For $m=7$ triples ($k=3$), greedily expand $7 = \binom{4}{3} + \binom{3}{2}$ ($a_3=4, a_2=3$). The minimum shadow size is:

$$ |\partial\mathcal F|\ge\binom{4}{2}+\binom{3}{1}=6+3=9. $$

Exercise. Find the minimum shadow size for five triples ($m=5, k=3$). Hint: $5 = \binom{4}{3} + \binom{2}{2}$. Solution: $|\partial \mathcal{F}| \ge \binom{4}{2} + \binom{2}{1} = 6 + 2 = 8$, attained by initial colex triples $\{123, 124, 134, 234, 125\}$.

18.5 Shadows and compression/shifting methods

What & Concept. Shifting (or compression) is an algorithmic technique that systematically replaces larger element labels with smaller absent labels ($j \to i$ with $i < j$) to transform an arbitrary set family into a highly structured shifted family.

Shifting Operator $S_{ij}$. For $1 \le i < j \le n$ and a family $\mathcal{F}$, define $S_{ij}(\mathcal{F})$ by replacing $A \in \mathcal{F}$ with $A' = (A \setminus \{j\}) \cup \{i\}$ whenever $j \in A$, $i \notin A$, and $A' \notin \mathcal{F}$. Otherwise, $A$ is retained.

Properties Preserved by Shifting:

1. Size & Uniformity: $|S_{ij}(\mathcal{F})| = |\mathcal{F}|$ and set cardinalities remain unchanged.
2. Intersecting Property: If $\mathcal{F}$ is intersecting, $S_{ij}(\mathcal{F})$ remains intersecting.
3. Shadow Inclusion: $\partial(S_{ij} \mathcal{F}) \subseteq S_{ij}(\partial \mathcal{F})$, meaning shifting never increases lower shadow size ($|\partial(S_{ij} \mathcal{F})| \le |\partial \mathcal{F}|$).

Termination Proof: Define integer potential $\Phi(\mathcal{F}) = \sum_{A \in \mathcal{F}} \sum_{x \in A} x$. Every successful shift $j \to i$ decreases $\Phi(\mathcal{F})$ by at least $j - i \ge 1$. Since $\Phi(\mathcal{F}) \ge 0$, shifting must terminate in finitely many steps, yielding a shifted family.

Exercise. Apply $S_{12}$ to $\mathcal{F} = \{23, 24, 34\}$. Hint: Check if target sets containing $1$ are already present. Solution: 23 $\to$ 13 (since 13 $\notin \mathcal{F}$); 24 $\to$ 14 (since 14 $\notin \mathcal{F}$); 34 stays 34 ($1 \notin 34$ and $2 \notin 34$). Result: $S_{12}(\mathcal{F}) = \{13, 14, 34\}$. Both families have size $3$ and shadow size $3$.

18.6 Sauer–Shelah lemma and VC dimension

What & Definitions. Let $\mathcal{F} \subseteq 2^{[n]}$ be a set family and $T \subseteq [n]$ a test set. The trace of $\mathcal{F}$ on $T$ is:

$$ \mathcal F|_T=\{A\cap T : A\in\mathcal F\}. $$

We say $\mathcal{F}$ shatters $T$ if its trace realizes every possible subset of $T$ ($\mathcal{F}|_T = 2^T$, yielding $|\mathcal{F}|_T| = 2^{|T|}$). The Vapnik–Chervonenkis (VC) dimension of $\mathcal{F}$, denoted $\operatorname{VCdim}(\mathcal{F})$, is the maximum size $|T|$ of a shattered test set $T$.

Application in Machine Learning: In statistical learning theory, $\mathcal{F}$ represents a binary hypothesis class. VC dimension measures classification flexibility: a hypothesis class with VC dimension $d$ can fit arbitrary binary labels on $d$ points, but cannot overfit arbitrary labels on $d+1$ points.

Sauer–Shelah Lemma (1972). If $\mathcal{F} \subseteq 2^{[n]}$ has VC dimension $\operatorname{VCdim}(\mathcal{F}) \le d$, then its cardinality is strictly bounded by:

$$ |\mathcal F|\le\sum_{i=0}^{d}\binom ni. $$

The upper bound is attained by taking the family of all subsets of size at most $d$ ($\mathcal{F} = \bigcup_{i=0}^d \binom{[n]}{i}$).

Solved Example. Let $\mathcal{F}$ consist of $\varnothing$ and all contiguous intervals on ordered set $[4]$. $|\mathcal{F}| = 1 + 4 + 3 + 2 + 1 = 11$. Any 2 points can be shattered, but no 3 ordered points $a < b < c$ can be shattered (an interval containing $a$ and $c$ must contain $b$, so trace subset $\{a,c\}$ is impossible). Thus $\operatorname{VCdim}(\mathcal{F}) = 2$, matching the Sauer–Shelah bound $\binom{4}{0} + \binom{4}{1} + \binom{4}{2} = 1 + 4 + 6 = 11$.

Exercise. What is the VC dimension of the family of prefixes $\mathcal{F} = \{\varnothing, \{1\}, \{1,2\}, \ldots, [n]\}$ on $[n]$ ($n \ge 1$)? Hint: Can any 2 points be shattered? Solution: On any 2 points $x < y$, subset $\{y\}$ can never appear without $x$. Thus $\operatorname{VCdim}(\mathcal{F}) = 1$, and $|\mathcal{F}| = n + 1 = \binom{n}{0} + \binom{n}{1}$.

18.7 Erdős–Rado sunflower lemma

What & Definitions. An $r$-sunflower (or $\Delta$-system) is a collection of $r$ distinct sets $A_1, A_2, \ldots, A_r$ such that every pairwise intersection $A_i \cap A_j$ ($i \ne j$) equals the exact same set $C$, called the core. The sets $P_i = A_i \setminus C$ are called petals, and they are pairwise disjoint ($P_i \cap P_j = \varnothing$). The core $C$ may be empty (disjoint sets form a sunflower with empty core).

Classical Sunflower Lemma (Erdős–Rado, 1960). If $\mathcal{F}$ is a $k$-uniform family containing strictly more than $k!(r-1)^k$ sets, then $\mathcal{F}$ guarantees the existence of an $r$-sunflower.

Proof Sketch (Induction on $k$): For $k=1$, $1!(r-1)^1 = r-1$ singletons. Having $> r-1$ singletons directly provides $r$ disjoint sets (an $r$-sunflower with empty core). For $k > 1$, take a maximal collection of pairwise disjoint sets in $\mathcal{F}$. If this collection has size $\ge r$, we are done. Otherwise, the union $X$ of these disjoint sets has size $|X| \le k(r-1)$. By Pigeonhole Principle, some element $x \in X$ must be contained in at least $|\mathcal{F}| / |X| > \frac{k!(r-1)^k}{k(r-1)} = (k-1)!(r-1)^{k-1}$ sets. Deleting $x$ yields a $(k-1)$-uniform family that contains an $r$-sunflower by induction; restoring $x$ yields an $r$-sunflower with core containing $x$.

Exercise. Compute the classical Erdős–Rado threshold for a 3-uniform family ($k=3$) to guarantee a 4-sunflower ($r=4$). Solution: $3!(4-1)^3 = 6 \times 27 = 162$. Thus, any 3-uniform family with at least 163 sets contains a 4-sunflower.

18.8 Boolean-cube isoperimetric inequalities

What & Definitions. The $n$-dimensional Boolean hypercube graph $Q_n = (V, E)$ has vertex set $V = \{0,1\}^n$ ($2^n$ vertices). Two binary vectors are connected by an edge if they differ in exactly one coordinate (Hamming distance 1).

For a subset of vertices $\mathcal{A} \subseteq V$ of size $m = |\mathcal{A}|$, we measure two distinct boundaries:

• Edge Boundary $\partial_E \mathcal{A}$: The set of edges with one endpoint inside $\mathcal{A}$ and one endpoint outside $\mathcal{A}$.
• External Vertex Boundary $\partial_V \mathcal{A}$: The set of vertices outside $\mathcal{A}$ that are adjacent to at least one vertex in $\mathcal{A}$.

Edge-Isoperimetric Inequality. For any set $\mathcal{A} \subseteq \{0,1\}^n$ of size $m = |\mathcal{A}|$, the number of boundary edges satisfies:

$$ |\partial_E\mathcal A|\ge m\log_2(2^n/m). $$

Equality holds whenever $m = 2^d$ and $\mathcal{A}$ is a $d$-dimensional subcube (formed by fixing $n-d$ coordinates).

Harper's Vertex-Isoperimetric Theorem (1966). To minimize the external vertex boundary $|\partial_V \mathcal{A}|$ for a given size $m$, $\mathcal{A}$ should be chosen as an initial segment of simplicial order (first ordering vertices by increasing set size, then lexicographically within each layer). In particular, complete Hamming balls minimize vertex boundary.

Exercise. In $Q_4$, fix the fourth coordinate to $0$. Count both the edge boundary and vertex boundary of the resulting 3D subcube. Hint: $n=4, d=3, m=8$. Solution: Each of the $8$ vertices has exactly $1$ neighbor with fourth coordinate $1$. Thus, $|\partial_E \mathcal{A}| = 8$ and $|\partial_V \mathcal{A}| = 8$, matching $8 \log_2(16/8) = 8$.

18.9 Littlewood–Offord inequalities

What & Concept. Consider $n$ real vectors or numbers $a_1, a_2, \ldots, a_n$ with $|a_i| \ge 1$. Let $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n \in \{-1, +1\}$ be independent uniform random signs. Define the random linear combination sum $S = \sum_{i=1}^n a_i \varepsilon_i$. Anti-concentration asks: What is the maximum probability that $S$ lands in a target interval $I$ of length $< 2$?

Connection to Order Theory: Map each sign vector $\varepsilon$ to the subset $A = \{i \in [n] : \varepsilon_i = +1\}$. The sum function $s(A) = 2 \sum_{i \in A} a_i - \sum_{i=1}^n a_i$ is strictly monotone along set inclusion ($A \subset B \implies s(B) - s(A) = 2 \sum_{i \in B \setminus A} a_i \ge 2$). Therefore, any collection of sign vectors whose sums fall into an open interval $I$ of length $< 2$ must form an antichain in $2^{[n]}$.

Littlewood–Offord Theorem (1943 / Sperner Proof by Erdős, 1945). For any real numbers $a_1, \ldots, a_n$ with $|a_i| \ge 1$ and any open interval $I$ of length $< 2$:

$$ \Pr(S\in I)\le 2^{-n}\binom{n}{\lfloor n/2\rfloor}. $$

Solved Example. For $n=4$ and $a_1=a_2=a_3=a_4=1$, the $2^4 = 16$ random sign sums yield counts: $-4$ (1), $-2$ (4), $0$ (6), $+2$ (4), $+4$ (1). The point probability $\Pr(S=0) = 6/16 = 3/8$, exactly matching $2^{-4} \binom{4}{2} = 6/16$.

Exercise. For coefficients $a = (1, 2, 4)$, find the maximum single-point probability $\max_x \Pr(S=x)$. Hint: Are all 8 signed sums distinct? Solution: The 8 sums are $\pm 1 \pm 2 \pm 4 \in \{-7, -5, -3, -1, 1, 3, 5, 7\}$. All 8 sums are distinct, so $\Pr(S=x) = 1/8$ for all $x$, strictly below the theoretical Sperner bound $2^{-3} \binom{3}{1} = 3/8$.

18.10 Stability and forbidden-configuration problems

What & Concept. While extremal theorems establish exact maximum bounds (such as Sperner's $M = \binom{n}{\lfloor n/2 \rfloor}$), stability theory asks: If a set family $\mathcal{F}$ is almost extremal in size ($|\mathcal{F}| \ge (1-\delta)M$), must $\mathcal{F}$ structurally resemble the unique extremal configuration?

Rank-Stability Consequence of LYM. Let $M = \binom{n}{\lfloor n/2 \rfloor}$ and $M'$ be the second largest layer size in $2^{[n]}$. If an antichain $\mathcal{F}$ has size $|\mathcal{F}| \ge (1-\delta)M$, let $r$ be the number of elements in $\mathcal{F}$ outside the middle layer(s). Substituting into LYM yields:

$$ 1 \ge L(\mathcal{F}) \ge \frac{|\mathcal{F}| - r}{M} + \frac{r}{M'} = \frac{|\mathcal{F}|}{M} + r \left( \frac{1}{M'} - \frac{1}{M} \right). $$

Rearranging gives an explicit upper bound on off-middle elements:

$$ r \le \frac{\delta}{\frac{1}{M'} - \frac{1}{M}}. $$

This proves that as $\delta \to 0$, $r \to 0$, forcing nearly all elements of an almost-extremal antichain to concentrate in the middle layer.

Exercise. On $[5]$, compare the maximum size of an antichain with the maximum size of a family with VC dimension $\le 1$. Hint: Use Sperner's Theorem and the Sauer–Shelah Lemma separately. Solution: Maximum antichain size is $\binom{5}{2} = 10$ (attained by all 2-element sets). Maximum size for VC dimension $\le 1$ is $\binom{5}{0} + \binom{5}{1} = 1 + 5 = 6$ (attained by all prefixes). The two constraints yield completely different extremal structures.

Compress a set family and test an extremal bound

The investigation joins three questions: what a compression preserves, what an exact extremal theorem proves, and what almost-extremal size tells us about shape. Throughout, digit strings denote sets rather than numbers.

Connecting size and structure. Sperner tells us the largest possible antichain size. LYM explains why ranks away from the middle use capacity faster, and Section 18.10 turns this explanation into a quantitative rank-stability estimate. Kruskal–Katona answers a different question about the overlap among smaller subsets forced by a uniform family. A family can be an antichain without being extremal in size, and it can be shifted without being extremal in shadow size.

A software application. Suppose a monotone feature rule remains true when more features are enabled. Its inclusion-minimal satisfying configurations form an antichain: if one contained another, the larger could not be minimal. For four features, at most six such configurations exist, with the rule “at least two features enabled” attaining the bound through its six minimal pairs. In general Sperner bounds how large a complete list of minimal witnesses can become. Near a maximum, the Lubell cost analysis begins to constrain their sizes. This is a structural and representation-size guarantee; finding the witnesses efficiently is a separate algorithmic question.

Before applying a result elsewhere, identify the ground set, the precise family restriction, and the quantity being optimized. Forbidden containment, forced intersection, bounded shattering, and boundary minimization each require their own hypotheses.