TAOCP 7.2.2.2 Exercise 241

Section 7.2.2.2: Satisfiability

Exercise 241. [20] Show that any set of at most $m/3000$ pigeons can be matched to distinct holes, under the restricted pigeonhole constraints $G_0$ of Theorem B.

Verified: yes
Solve time: 6m09s

$$ \textbf{Solution.} $$

Let $P$ be a set of pigeons with

$$ |P|\leq \frac{m}{3000}. $$

We regard the restricted pigeonhole constraints $G_0$ as a bipartite graph. The left vertices are the pigeons, the right vertices are the holes, and an edge $p h$ means that the constraint system allows pigeon $p$ to be assigned to hole $h$.

We prove that every such $P$ satisfies Hall's condition. Let $S\subseteq P$ be arbitrary, and write $\Gamma(S)$ for the set of holes adjacent to at least one pigeon in $S$.

Because

$$ S\subseteq P, $$

we have

$$ |S|\leq |P|\leq \frac{m}{3000}. $$

The graph $G_0$ supplied by Theorem B satisfies the strong expansion condition (108). In the notation of that theorem, every set of pigeons $S$ with

$$ |S|\leq \frac{m}{3000} $$

has a neighborhood $\Gamma(S)$ large enough that

$$ |\Gamma(S)|\geq |S|. $$

The reason this applies here is that $S$ is an arbitrary subset of $P$, and the only hypothesis needed for the expansion conclusion is the upper bound on the size of $S$. Therefore every subset of $P$ satisfies

$$ |\Gamma(S)|\geq |S|. $$

Hence the bipartite graph induced by $P$ and the holes of $G_0$ satisfies Hall's condition. By Hall's marriage theorem, there exists a matching that covers every pigeon in $P$. Equivalently, every pigeon in $P$ can be assigned to a distinct hole using only the allowed edges of $G_0$.

Since $P$ was an arbitrary set of pigeons satisfying

$$ |P|\leq \frac{m}{3000}, $$

every set of at most $m/3000$ pigeons can be matched to distinct holes under the restricted pigeonhole constraints $G_0$. $\square$