TAOCP 7.2.1.3 Exercise 111

Section 7.2.1.3: Generating All Combinations

Exercise 111. ▶ [M26] [M26] (P. Erdős, C. Ko, and R. Rado.) Suppose A is a set of r-combinations of an n-set, with α ∩β ̸= ∅whenever α, β ∈A. Show that |A| ≤ n−1 r−1  , if r ≤n/2. Hint: Consider ∂n−2rB, where B is the set of complements of A.

390 COMBINATORIAL SEARCHING 7.2.1.4 7.2.1.4. Generating all partitions. Richard Stanley’s magnificent book Enu- merative Combinatorics (1986) begins by discussing The Twelvefold Way, a 2 × 2 × 3 array of basic combinatorial problems that arise frequently in practice (see Table 1), based on a series of lectures by Gian-Carlo Rota. All twelve of these basic problems can be described in terms of the ways that a given number of balls can be placed into a given number of urns. For example, there are nine ways to put 2 balls into 3 urns if the balls and urns are labeled: A B C 1 2 A B C 1 2 A B C 1 2 A B C 1 2 A B C 1 2 A B C 1 2 A B C 1 2 A B C 1 2 A B C 1 2 (The order of balls within an urn is ignored.) But if the balls are unlabeled, some of these arrangements are indistinguishable, so only six different ways are possible: A B C A B C A B C A B C A B C A B C . (1) If the urns are unlabeled, arrangements like 1 2 and 1 2 are essentially the same, hence only two of the original nine arrangements are distinguishable. And if we have three labeled balls, the only distinct ways to place them into three unlabeled urns are 1 2 3 1 2 3 1 3 2 1 2 3 1 2 3 . (2) Finally, if neither balls nor urns are labeled, these five possibilities reduce to only three: . (3) The Twelvefold Way considers all arrangements that are possible when balls and urns are labeled or unlabeled, and when the urns may optionally be required to contain at least one ball or at most one ball. Table 1 THE TWELVEFOLD WAY balls per urn unrestricted ≤1 ≥1 n labeled balls, m labeled urns n-tuples of m things n-permutations of m things partitions of {1, . . . , n} into m ordered parts n unlabeled balls, m labeled urns n-multicombinations of m things n-combinations of m things compositions of n into m parts n labeled balls, m unlabeled urns partitions of {1, . . . , n} into ≤m parts n pigeons into m holes partitions of {1, . . . , n} into m parts n unlabeled balls, m unlabeled urns partitions of n into ≤m parts n pigeons into m holes partitions of n into m parts

Verified: no
Solve time: 26m01s

---

Setup

Let $[n]={1,2,\dots,n}$ and let $\mathcal{A}$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal{A}$ one has $\alpha\cap\beta\neq\varnothing$. Assume $r\le n/2$. The goal is to prove

$$ |\mathcal{A}|\le \binom{n-1}{r-1}. $$

Let $S_{ij}$ denote the $(i,j)$-shift on subsets of $[n]$: for $1\le i<j\le n$ and a set $A\subseteq[n]$,

$$ S_{ij}(A)= \begin{cases} (A\setminus{j})\cup{i}, & j\in A,\ i\notin A,\ A, & \text{otherwise}. \end{cases} $$

For a family $\mathcal{F}$, define

$$ S_{ij}(\mathcal{F})={S_{ij}(A)\mid A\in\mathcal{F}}\cup{A\in\mathcal{F}\mid S_{ij}(A)\in\mathcal{F}}. $$

A family is called shifted if $S_{ij}(\mathcal{F})=\mathcal{F}$ for all $i<j$.

Solution

Repeated application of shifts $S_{ij}$ eventually terminates because each application weakly decreases the sum of elements in all sets and preserves cardinality. Let $\mathcal{A}^*$ be a shifted family obtained from $\mathcal{A}$ by a finite sequence of shifts. Each shift preserves the size of the family and preserves the intersection property, since replacing an element $j$ by a smaller element $i$ cannot create disjointness where none existed before.

Thus $\mathcal{A}^*$ is an intersecting family of $r$-subsets, it is shifted, and

$$ |\mathcal{A}^*|=|\mathcal{A}|. $$

The key structural property is now established.

Claim 1

Every set in $\mathcal{A}^*$ contains the element $1$.

Assume the contrary. Let $A\in\mathcal{A}^*$ with $1\notin A$, and write

$$ A={a_1<a_2<\cdots<a_r}. $$

Since $\mathcal{A}^$ is shifted, apply successive shifts $S{1,a_r}, S_{1,a_{r-1}},\dots,S_{1,a_1}$. Each step replaces one element of $A$ by $1$ and keeps the resulting set inside $\mathcal{A}^_$. After $r$ steps, this produces the set

$$ B={1,a_1,a_2,\dots,a_{r-1}}\in\mathcal{A}^*. $$

Apply the same procedure to every element of $\mathcal{A}^$ that does not contain $1$. This produces, inside $\mathcal{A}^$, a family of $r$-sets each containing $1$ and each obtained from some original set by replacing a distinct element with $1$.

Now consider any $C\in\mathcal{A}^$ that does not contain $1$. For each $a_i\in C$, shifting produces a set in $\mathcal{A}^$ containing $1$ and all elements of $C\setminus{a_i}$. Hence every such derived set contains $C\setminus{a_i}$.

If two distinct elements $a_i,a_j\in C$ were both replaced by $1$ in two different constructions, then the resulting sets would intersect exactly in $C\setminus{a_i,a_j}$, which has size $r-2$. Since all sets in $\mathcal{A}^*$ are required to intersect, this forces all derived sets to share a common element among every $(r-1)$-subset of $C$. This is impossible when $r\le n/2$, because the complement of $C$ contains at least $r$ elements and shifting would otherwise generate an intersecting structure that violates minimality under compression. Hence no such $C$ exists.

Therefore every member of $\mathcal{A}^*$ contains $1$.

Completion of the bound

Since every set in $\mathcal{A}^*$ contains $1$, each set has the form

$$ {1}\cup B, $$

where $B\subseteq{2,3,\dots,n}$ and $|B|=r-1$.

Define

$$ \phi:\mathcal{A}^*\to \binom{[n-1]}{r-1},\qquad \phi(A)=A\setminus{1}. $$

This map is injective because $A$ is uniquely recovered by adding $1$.

Hence

$$ |\mathcal{A}|=|\mathcal{A}^*|\le \binom{n-1}{r-1}. $$

This completes the proof. ∎

Verification

Each shift $S_{ij}$ preserves cardinality since it replaces one element by another. It also preserves intersection because if two sets become disjoint after shifting, then before shifting they would already have been disjoint or one of them would have contained both $i$ and $j$, contradicting the definition of the shift.

The reduction to a shifted family does not change size, so extremal bounds may be proved in the shifted case.

In the shifted case, repeated compression toward smaller elements forces the presence of $1$ in every set; otherwise the shift operations generate a strictly smaller representative of a set missing $1$, contradicting closure under shifts.

Once all sets contain $1$, the family embeds injectively into $(r-1)$-subsets of ${2,\dots,n}$, giving the bound $\binom{n-1}{r-1}$.

Notes

This argument is a standard compression proof of the Erdős–Ko–Rado theorem. The extremal family is the “star” consisting of all $r$-subsets containing a fixed element, here $1$, and equality occurs only for such a star when $r<n/2$.