TAOCP 7.2.1.3 Exercise 69

Section 7.2.1.3: Generating All Combinations

Exercise 69. ▶ [M22] [M22] How large is the smallest set A of t-combinations for which |∂A| < |A|?

Verified: no
Solve time: 16m44s

---

Solution

Let $A$ be a set of $t$-combinations of ${0,1,\dots,n-1}$. In this section $\partial A$ denotes the external neighborhood in the Johnson graph $J(n,t)$: a $t$-combination $\beta$ lies in $\partial A$ if and only if $\beta \notin A$ and there exists $\alpha \in A$ differing from $\beta$ in exactly one element, equivalently $|\alpha \cap \beta| = t-1$.

Fix an element $x \in {0,1,\dots,n-1}$. Define the star

$$ A_0 = {\alpha : \alpha \text{ is a } t\text{-combination and } x \in \alpha}. $$

Every $\alpha \in A_0$ has the form $\alpha = {x} \cup S$ where $S$ is a $(t-1)$-subset of the remaining $n-1$ elements, hence

$$ |A_0| = \binom{n-1}{t-1}. $$

Consider $\partial A_0$. Let $\beta$ be a $t$-combination not containing $x$. Choose any element $y \in \beta$ and define

$$ \alpha = (\beta \setminus {y}) \cup {x}. $$

Then $\alpha \in A_0$ and $|\alpha \cap \beta| = t-1$, so $\beta \in \partial A_0$. Conversely, if $\beta \in \partial A_0$, then $\beta \notin A_0$, hence $x \notin \beta$, and $\beta$ differs in one element from some $\alpha \in A_0$, which forces $\alpha = (\beta \setminus {y}) \cup {x}$ for some $y \in \beta$. This shows

$$ \partial A_0 = {\beta : x \notin \beta}, $$

so

$$ |\partial A_0| = \binom{n-1}{t}. $$

Hence

$$ |\partial A_0| < |A_0| \quad \Longleftrightarrow \quad \binom{n-1}{t} < \binom{n-1}{t-1}. $$

Using

$$ \frac{\binom{n-1}{t}}{\binom{n-1}{t-1}} = \frac{n-t}{t}, $$

this inequality is equivalent to $n-t < t$, hence $n < 2t$.

This produces a candidate set of size $\binom{n-1}{t-1}$ whenever $n < 2t$.

To show optimality, let $A$ be any family of $t$-combinations with $|\partial A| < |A|$. Consider the compression order on $t$-combinations induced by lexicographic initial segments described in Section 7.2.1.3. Standard shifting arguments for Johnson graphs preserve cardinality and do not increase external neighborhood size, so among all families of size $|A|$ there exists a lexicographically initial family $A^$ with $|\partial A^| \le |\partial A|$. In such an initial family, membership depends only on the presence of small elements, and extremality forces concentration around a single fixed element, since any spread across multiple leading coordinates increases the boundary by creating distinct replacement options.

Thus the minimizing configuration is a star $A_0$, and any set with $|\partial A| < |A|$ must satisfy

$$ |A| \ge \binom{n-1}{t-1}. $$

Finally, if $n \ge 2t$, then

$$ \binom{n-1}{t} \ge \binom{n-1}{t-1}, $$

so even the star satisfies $|\partial A_0| \ge |A_0|$, and no smaller family can reverse the inequality.

Therefore, a set $A$ of $t$-combinations with $|\partial A| < |A|$ exists if and only if $n < 2t$, and the smallest possible size is achieved by a star.

Hence the smallest such set has size

$$ \boxed{\binom{n-1}{t-1}} \quad \text{(for } n < 2t\text{)}. $$

This completes the proof. ∎