4.2: Existence of SDRs

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\}.\nonumber$$ 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\}.\nonumber$$

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 $\PageIndex{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}|.\nonumber$$ 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}|\nonumber$$ 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.\nonumber$$ 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. }\nonumber$$ Thus, $B_{k+1},\ldots,B_{n}$ has an sdr, which finishes the proof.