# 4.1: Existence of SDRs

- Page ID
- 7160

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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.

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.

\(\square\)