## Bipartite matchings and SDRs

Matchings in bipartite graphs and systems of distinct representatives (SDRs) of systems of subsets are closely related. More precisely, let $\mathcal{A}=\{A_1,...,A_m\}\subseteq 2^X,$ for $X$ a finite set. We can construct a bipartite graph $\Gamma=(\mathcal{A}\cup X,E),$ where $E=\{(A,x)\mid x\in A\in\mathcal{A}\}.$

An SDR of $\mathcal{A}$ is $Y\subseteq X$ such that $A_i\cap A_j\cap Y=\emptyset$ for all $i\neq j$ and $|A_i\cap Y|=1$ for all $i.$ In particular $Y$ contains exactly one element $y_A$ for each $A\in\mathcal{A}.$
Then $\{(A,y_A)\mid A\in\mathcal{A}\}$ is a matching of $\Gamma$ saturating the part $\mathcal{A}.$ In particular, it is a maximum matching.
Conversely, a matching of $\Gamma$ saturating $\mathcal{A}$ gives rise to an SDR for $\mathcal{A}.$

An obvious necessary condition for existing of an SDR for $\mathcal{A}$
is the following Hall’s condition:

$| \cup_{A\in\mathcal{B}} A|\geq |\mathcal{B}|,\qquad \forall\ \mathcal{B}\subseteq\mathcal{A}.$

In view of this, Hall’s Theorem for matchings is equivalent to the following

An SDR for $\mathcal{A}$ exists iff it satisfies Hall’s condition.

To see that Hall’s condition is sufficient, we proceed by induction on $m.$ For $m=1$ the claim is obvious. Assume that it is true for all collections of less than $m$ sets. We now establish that it holds for $m$-set collections, too.

If $| \cup_{A\in\mathcal{B}} A|> |\mathcal{B}|,\quad \forall\ \mathcal{B}\subset\mathcal{A},$ then we take any $A\in \mathcal{A}$ and set $y_A=y$ for some $y\in A.$ Now by induction there is an SDR $Y'$ for $\mathcal{A}\setminus\{A\}.$ Then $\{y_A\}\cup Y'$ is an SDR for $\{B\setminus\{y_A\}\mid B\in\mathcal{A}\}.$

In the remaining case there exists $k< m$ such that $| \cup_{A\in\mathcal{B}} A|=|\mathcal{B}|=k,\quad \mathcal{B}\subset\mathcal{A}.$ By induction, there is an SDR $Y'$ for $\mathcal{B}.$
Let $\mathcal{C}\subseteq \mathcal{A}\setminus\mathcal{B}.$ Then $| \cup_{A\in\mathcal{C}} A\setminus Y'|\geq |\mathcal{C}|=s,$ for otherwise $| \cup_{A\in\mathcal{C}\cup\mathcal{B}} A|< s+k,$ contradicting Hall’s condition. Now we can take an SDR $Y''$ for $\{A\setminus Y'\mid A\in\mathcal{A}\setminus\mathcal{B},$ and observe that $Y'\cup Y''$ is an SDR for $\mathcal{A}.$