# Statements > [!NOTE] Theorem (Hall, Marriage Theorem) > A *set system* $A_{1},\dots,A_{n}$ has an [[System of Distinct Representatives|SDR]] iff for every $k=1,\dots n$, $\forall \{ i_{1},\dots,i_{k} \} \subseteq \{ 1,\dots, n \}, \qquad \left\lvert \bigcup_{j= 1}^{k} A_{i_{j}} \right\rvert \geq k. $(This condition is known as *Hall's condition*). > > We may rewrite this as $\forall I \subset [n], \qquad \left\lvert \bigcup_{i\in I} A_{i} \right\rvert \geq \lvert I \rvert. $ Let $G=(V,E)$ be a bipartite graph of so that $L,R$ is a partition of $V$ and $\{ u,v \}\in E\iff (u\in L \implies v\in R).$ WLOG suppose $n:=|L|<|R|$ then there exist a matching of $G$ if and only if $|N(A)|\geq |A|$ for all $A\subset L,$ where $N(A)=\cup_{v\in A} N(v).$ # Proofs ###### Proof of SDR formulation by induction Consider a set system with universe $X$ and sets $A_{1},\dots,A_{n}$. ($\implies$) Suppose that the system has an SDR, given by $\{ x_{1},\dots,x_{n} \}\subseteq X$. Assume that for every $x_{i}\in A_{i}$. For any $I\subset[n]$ $\bigcup_{i\in I} \{ x_{i} \} \subseteq \bigcup_{i\in I} A_{i}$which shows that $\left\lvert \bigcup_{i\in I} A_{i} \right\rvert \geq \lvert I \rvert$ ($\Longleftarrow$) We prove the converse by [[Induction Principle|induction]] on the number of sets $n$. In the base case, $n=1$. Hall's condition being satisfied implies that the only set in the system $A_{1}$ is non-empty. Hence we have an obvious SDR in the system. Now let $n>1$ and suppose that the theorem is true: for every collection of $k<n$ that satisfies Hall's condition, there is an SDR. Suppose we have set sets $A_{1},\dots,A_{n}$ satisfying Hall's condition. We need to show there is an SDR. Consider the following cases: **Case 1**: Suppose that for every $k< n$ and every $\{ i_{1},\dots,i_{k} \}\subseteq[n]$, that $\left\lvert \bigcup_{j=1}^{k} A_{i_{j}} \right\rvert \geq k+1$, *that is these unions are larger than required.* Pick any element $x_{n}\in A_{n}$, and define $B_{i}=A_{i}\setminus \{ x_{n} \}$ for each $i<n$. Consider the collection of sets $B_{1},\dots,B_{n-1}$, and any union $\bigcup_{j=1}^{k} B_{i_{j}}$. 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}} \setminus \{ x_{n} \}$ so $\left\lvert \bigcup_{j=1}^{k} B_{i_{j}} \right\rvert$ equals $\left\lvert \bigcup_{j=1}^{k} A_{i_{j}} \right\rvert$ or $\left\lvert \bigcup_{j=1}^{k} A_{i_{j}} \right\rvert-1$. Either way $\left\lvert \bigcup_{j=1}^{k} B_{i_{j}} \right\rvert \geq k$ since $\left\lvert \bigcup_{j=1}^{k} A_{i_{j}} \right\rvert \geq k+1$. Thus, by induction hypothesis, the collection $B_{1},\dots,B_{n-1}$ has an SDR $\{ x_{1},\dots,x_{n-1} \}$. By definition of the $B_{i}$, for every $i<n$, $x_{i}\neq x_{n}$ so $\{ x_{1},\dots,x_{n} \}$ is an SDR for $A_{1},\dots,A_{n}$. **Case 2**: Otherwise, for some $k\in[n-1]$, there exists $\{i_{1},\dots, i_{k}\} \subseteq [n]$ such that $\left\lvert \bigcup_{j=1}^{k} A_{i_{j}} \right\rvert \leq k$. Note that the original set system satisfies Hall’s condition so $\left\lvert \bigcup_{j=1}^{k} A_{i_{j}} \right\rvert = k$. WLOG, assume $\lvert \cup_{j=1}^{k} A_{j} \rvert=k$. By induction hypothesis, $A_{1},\dots,A_{k}$ has an SDR $\{ x_{1},\dots,x_{k} \}$. Define $B_{i}=A_{i} \setminus \cup_{j=1}^{k} A_{j}$ for $k<i\leq n$. Suppose $\{ x_{k+1},\dots,x_{n} \}$ is an SDR for $B_{k+1},\dots,B_{n}$ then it is also an SDR for $A_{k+1},\dots,A_{n}$. Moreover, $\{ x_{1},\dots,x_{n} \}$ is an SDR for $A_{1},\dots,A_{n}$. Thus STP $B_{k+1},\dots,B_{n}$ satisfy Hall's condition. Consider some sets $B_{i_{1}},\dots,B_{i_{l}}$. First notice that $\lvert A_{1} \cup A_{2}\cup\dots \cup A_{k} \cup B_{i_{1}} \cup B_{i_{2}} \cup \dots B_{i_{l}} \rvert = k + \lvert B_{i_{1}} \cup B_{i_{2}} \cup \dots B_{i_{l}} \rvert .$Also $\lvert A_{1} \cup A_{2}\cup\dots \cup A_{k} \cup B_{i_{1}} \cup B_{i_{2}} \cup \dots B_{i_{l}} \rvert = \lvert A_{1} \cup A_{2} \cup \dots \cup A_{k} \cup A_{i_{1}} \cup \dots A_{i_{l}} \rvert $thus $\lvert A_{1} \cup A_{2} \cup \dots \cup A_{k} \cup A_{i_{1}} \cup \dots A_{i_{l}} \rvert \geq k+l.$Putting these together gives $\begin{array}{c}k+|B_{i_1}\cup B_{i_2}\cup\cdots\cup B_{i_1}|\geq k+l\\|B_{i_1}\cup B_{i_2}\cup\cdots\cup B_{i_1}|\geq l\end{array}$Thus, $B_{k+1},\dots,B_{n}$ has an SDR. $\square$ ###### Proof of graph formulation Suppose the elements of $L$ denotes set and those of $R$ denote the set universe. Then there exists a maximum matching iff the set system has a system of distinct representatives. Thus the result follows from above. # Applications > [!Example]- Examples >1. Let $r\in\mathbb{N}$. Suppose that a set system with universe $X$ and sets $A_1,A_2,\ldots,A_n$ has the property that each of these sets contain exactly $r$ elements and moreover, no element appears in more than $r$ of the sets. Prove that this set system has a system of distinct representatives. >2. We have a standard deck of $52$ playing cards, with exactly $4$ cards of each of the $13$ ranks. Someone gives you these cards in the form of $13$ piles, each with $4$ cards in it. Prove that there is a way to take a card from each pile in a such a way that we would have a card of each rank. >3. Let $r\in\mathbb{N}$, sets $A_1,A_2,\ldots,A_n\subseteq X.$ Suppose that this system satisfies the following property. For every $1\leq k\leq n$ and distinct indices $\{i_1,i_2,\ldots,i_k\}\subseteq$ $[n],|\bigcup_{j=1}^kA_{i_j}|\geq k-r.$ Show that there exists a collection of distinct indices $\{i_1,\ldots,i_{n-r}\}$ such that the set system with universe $X$ and sets $A_{i_1},\ldots,A_{i_{n-r}}$ has a system of distinct representatives. > [!Warning]- Solutions > 4. STS the set system satisfies Hall's condition: for every $k=1,\dots,n$ and $\{ i_{1},\dots,i_{k} \}\subseteq \{ 1,\dots,n \},$ we have that $|\bigcup_{j=1}^{k} A_{i_{j}}|\geq k.$ If $k\leq r,$ then the sets indeed satisfy Hall's condition. > Now suppose $k>r.$ Let $Y$ be the multiset obtained by the union of $A_{1},\dots,A_{ik}.$ It follows that $Y$ has size exactly $rk.$ On the other hand, since every element appears in an most $r$ sets in the set system, each element occurs at most $r$ times in the multiset $Y.$ Hence, there must be at least $k$ distinct elements in the multiset $Y,$ implying that $|\bigcup_{j=1}^{k} A_{i_{j}}|\geq k.$ $\square$ > > 5. Let us name the ranks $r_{1},\dots,r_{13}$ and the piles $p_{1},\dots,p_{13}.$ Then define a set system $A_{1},\dots,A_{13}$ where $A_{i}=\{ p_{j} \mid \text{the pile $p_{j}$ contains a card of rank $r_{i}$ for } 1 \leq j \leq 13 \}.$STS that the system satisfies Hall's condition. For $k=1,\dots,13$ and $\{ i_{i}, \dots, i_{k} \}\subseteq \{ 1,\dots,13 \},$ let $Z = \bigcup_{j=1}^{k} A_{i_{j}}.$ BWOC suppose $Z$ contains at most $k-1$ elements - that is all the cards of ranks $r_{i_{1}},\dots r_{i_{k}}$ appear in at most $k-1$ piles. There are a total of $4k$ cards of ranks $r_{i_{1}},\dots,r_{i_{k}}.$ On the other hand, each pile has $4$ cards so $Z$ accounts for at most $4(k-1)$ cards. $\square$ >