In this section, **sdr** means complete **sdr**.
It is easy to see that not every collection of sets has an **sdr**. For
example,
$$A_1=\{a,b\}, A_2=\{a,b\}, A_3=\{a,b\}.$$
The problem is clear: there are only two possible representatives, so
a set of three distinct representatives cannot be found. This example
is a bit more general than it may at first appear. Consider
$$A_1=\{a,b\}, A_2=\{a,b\}, A_3=\{a,b\}, A_4=\{b,c,d,e\}.$$
Now the total number of possible representatives is 5, and we only
need 4. Nevertheless, this is impossible, because the first three sets
have no **sdr** considered by themselves. Thus the following condition,
called **Hall's Condition**, is
clearly necessary for the existence of an **sdr**: For every $k\ge1$, and
every set $\{i_1,i_2,\ldots,i_k\}\subseteq [n]$,
$|\bigcup_{j=1}^k A_{i_j}|\ge k$. That is, the number of possible
representatives in any collection of sets must be at least as large as
the number of sets. Both examples fail to have this property
because $|A_1\cup A_2\cup A_3|=2< 3$.

Remarkably, this condition is both necessary and sufficient.

Theorem 4.1.1 (Hall's Theorem)
A collection of sets $A_1,A_2,\ldots,A_n$ has an **sdr** if and only
if for every $k\ge1$, and
every set $\{i_1,i_2,\ldots,i_k\}\subseteq [n]$,
$|\bigcup_{j=1}^k A_{i_j}|\ge k$.

**Proof.**
We already know the condition is necessary, so we prove sufficiency by
induction on $n$.

Suppose $n=1$; the condition is simply that $|A_1|\ge 1$. If this is
true then $A_1$ is non-empty and so there is an **sdr**. This
establishes the base case.

Now suppose that the theorem is true for a collection of $k< n$ sets,
and suppose we have sets $A_1,A_2,\ldots,A_n$ satisfying Hall's Condition.
We need to show there is an **sdr**.

Suppose first that for every $k< n$ and every
$\{i_1,i_2,\ldots,i_k\}\subseteq [n]$, that
$|\bigcup_{j=1}^k A_{i_j}|\ge k+1$, that is, that these unions are
larger than required. Pick any element $x_n\in A_n$, and define
$B_i=A_i\backslash\{x_n\}$ for each $i< n$. Consider the collection of
sets $B_1,\ldots,B_{n-1}$, and any union
$\bigcup_{j=1}^k B_{i_j}$ of a subcollection of the sets.
There are two possibilities: either $\bigcup_{j=1}^k
B_{i_j}=\bigcup_{j=1}^k A_{i_j}$ or $\bigcup_{j=1}^k
B_{i_j}=\bigcup_{j=1}^k A_{i_j}\backslash\{x_n\}$, so that
$|\bigcup_{j=1}^k
B_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|$ or
$|\bigcup_{j=1}^k
B_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|-1$. In either case, since
$|\bigcup_{j=1}^k A_{i_j}|\ge k+1$, $|\bigcup_{j=1}^k B_{i_j}|\ge k$.
Thus, by the induction hypothesis, the collection
$B_1,\ldots,B_{n-1}$ has an **sdr** $\{x_1,x_2,\ldots,x_{n-1}\}$, and for
every $i< n$, $x_i\not= x_n$, by the definition of the $B_i$. Thus
$\{x_1,x_2,\ldots,x_{n}\}$ is an **sdr** for $A_1,A_2,\ldots,A_n$.

If it is not true that for every $k< n$ and every
$\{i_1,i_2,\ldots,i_k\}\subseteq [n]$,
$|\bigcup_{j=1}^k A_{i_j}|\ge k+1$, then for some $k< n$ and
$\{i_1,i_2,\ldots,i_k\}$, $|\bigcup_{j=1}^k A_{i_j}|= k$.
Without loss of generality, we may assume that
$|\bigcup_{j=1}^k A_{j}|= k$.
By the induction hypothesis, $A_1,A_2,\ldots,A_k$ has an **sdr**,
$\{x_1,\ldots,x_k\}$.

Define $B_i=A_i\backslash \bigcup_{j=1}^k A_{j}$ for $i> k$.
Suppose that $\{x_{k+1},\ldots,x_{n}\}$ is
an **sdr**
for $B_{k+1},\ldots,B_{n}$; then it is also an **sdr** for
$A_{k+1},\ldots,A_{n}$. Moreover, $\{x_1,\ldots,x_n\}$ is an **sdr** for
$A_{1},\ldots,A_{n}$. Thus, to finish the proof it suffices to show
that $B_{k+1},\ldots,B_{n}$ has an **sdr**. The number of sets here is
$n-k< n$, so we need only show that the sets satisfy Hall's Condition.

So consider some sets $B_{i_1},B_{i_2},…,B_{i_l}$. First we notice
that
$$|A_1\cup A_2\cup\cdots\cup A_k\cup B_{i_1}\cup B_{i_2}\cup\cdots
B_{i_l}|=k+|B_{i_1}\cup B_{i_2}\cup\cdots
B_{i_l}|.$$
Also
$$|A_1\cup A_2\cup\cdots\cup A_k\cup B_{i_1}\cup B_{i_2}\cup\cdots
B_{i_l}|=|A_1\cup A_2\cup\cdots\cup A_k\cup A_{i_1}\cup A_{i_2}\cup\cdots
A_{i_l}|$$
and
$$|A_1\cup A_2\cup\cdots\cup A_k\cup A_{i_1}\cup A_{i_2}\cup\cdots
A_{i_l}|\ge k+l.$$
Putting these together gives
$$\eqalign{
k+|B_{i_1}\cup B_{i_2}\cup\cdots\cup B_{i_l}|&\ge k+l\cr
|B_{i_1}\cup B_{i_2}\cup\cdots\cup B_{i_l}|&\ge l\cr.
}$$
Thus, $B_{k+1},\ldots,B_{n}$ has an **sdr**, which finishes the proof.
$\qed$

## Exercises 4.1

**Ex 4.1.1**
How many different systems of distinct
representatives are there for $A_1=\{1,2\}$, $A_2=\{2,3\}$,
…, $A_n=\{n,1\}$?

**Ex 4.1.2**
How many different systems of distinct
representatives are there for
the sets $A_i=[n]\backslash{i}$, $i=1,2,\ldots,n$, $n\ge2$?

**Ex 4.1.3**
Suppose the set system $A_1,A_2,\ldots,A_n$ has an **sdr**,
and that $x\in A_i$. Show the set system has an **sdr** containing
$x$. Show that $x$ cannot necessarily be chosen to represent $A_i$.

**Ex 4.1.4**
Suppose the set system $A_1,A_2,\ldots,A_n$ satisfies
$|\bigcup_{j=1}^k A_{i_j}|\ge k+1$ for every $1\le k< n$ and
$\{i_1,i_2,\ldots,i_k\}\subseteq [n]$, and that $x\in A_i$. Show the
set system has an **sdr** in which $x$ represents $A_i$.

**Ex 4.1.5**
An $m\times n$ chessboard, with $m$ even and both $m$ and
$n$ at least 2, has one white and one black square removed. Show that
the board can be covered by dominoes.