6 System of distinct representatives 6 System of distinct representatives 6.2 Latin rectangles and decomposition of doubly stochastic matrices

6.1 Hall’s marriage theorem and SDR

Definition 6.1.

A subset $M$ of edges is said to be independent / matching if no two edges are incident on any vertex or equivalently, every vertex is contained in at most one edge. A complete matching $M$ on a subset $S\subset V$ is a matching that contains all the vertices in $S$ . A perfect matching is a complete matching on $G$ .

Alternatively one can consider a matching of a graph $M$ as a subgraph of $G$ such that $d_{M}(v)=1$ for all $v\in V(M)$ . A matching is perfect if $M$ is spanning. A vertex $v$ is said to be saturated if $v\in M$ and else unsaturated. For a subset $S\subset V$ , $N(S)=\bigcup_{v\in S}N(v).$

Theorem 6.2 (Hall’s marriage theorem ; Hall, 1935).

Let $G$ be a bi-partite graph with the two vertex sets being $V_{1},V_{2}$ . Then there exists a complete matching on $V_{1}$ iff $|N(S)|\geq|S|$ for all $S\subset V_{1}$ .

We will give a proof via induction now and a later exercise will involve proof using max-flow min-cut theorem. See [Diestel 2000, Section 2.1] for two more proofs.

Proof.

Let $|V_{1}|=k$ and our proof will be by induction on $k$ . If $k=1$ , the proof is trivial.

Let $G=V_{1}\cup V_{2}$ be such that the result holds for any graph with strictly smaller $V_{1}$ .

Suppose that $|N(S)|\geq|S|+1$ for all $S\subsetneq V_{1}$ . Then choose $(v,w)\in E\cap V_{1}\times V_{2}$ and consider the induced subgraph $G^{\prime}:=<V-\{v,w\}>$ . Since we have removed only $w$ from $V_{2}$ and that $|N(S)|\geq|S|+1$ for all $S\subsetneq V_{1}$ , we get that $|N(S^{\prime})|\geq|S^{\prime}|$ for all $S^{\prime}\subset V_{1}-\{v\}$ . Thus there is a complete matching $M$ on $V_{1}-\{v\}$ in $G^{\prime}$ by induction hypothesis and $M\cup(v,w)$ is a complete matching on $V_{1}$ in $G$ as desired.

If the above is not true i.e., there exists $A\subset V_{1}$ such that $N(A)=B$ and $|A|=|B|$ . Then, by induction hypothesis, there is a complete matching $M_{0}$ on $A$ in the induced subgraph $<A\cup B>$ . Trivially, Hall’s condition holds i.e., for all $S\subset A$ , $|N(S)\cap B|=|N(S)|\geq|S|$ . Let $G^{\prime}:=G-<A\cup B>$ . Let $S\subset V_{1}-A$ . Suppose if $|N^{\prime}(S)|<|S|$ where $N^{\prime}(S)=N(S)\cap(V_{2}-B)$ . Then, we have that $N(S\cup A)=N^{\prime}(S)\cup B$ and hence $|N(S\cup A)|\leq|N^{\prime}(S)|+|B|<|S|+|A|$ , a contradiction. Hence, $G^{\prime}$ also satisfies Hall’s condition and again by induction hypothesis $G^{\prime}$ has a complete matching $M^{\prime}$ on $V_{1}-A$ . Thus, we have a complete matching $M:=M_{0}\cup M^{\prime}$ on $V_{1}$ in $G$ . ∎

Exercise(A) 6.3.

For $k>0$ , a $k$ -regular bipartite graph has a perfect matching.

Proposition 6.4.

Let $d\geq 1$ . Let $G$ be a bipartite graph on $V_{1}\sqcup V_{2}$ such that $|N(S)|\geq|S|-d$ for all $S\subset V_{1}$ . Then $G$ has a matching with at least $|V_{1}|-d$ independent edges.

Proof.

Set $V^{\prime}_{2}:=V_{2}\cup[d]$ . Define $G^{\prime}$ with vertex set as $V_{1}\sqcup V^{\prime}_{2}$ and edge set as $E(G)\cup(V_{1}\times[d])$ . Then, it is easy to see that Hall’s condition is true on $G^{\prime}$ and hence there is a complete matching $M$ of $V_{1}$ in $G^{\prime}$ . Now, if we remove the edes in $M$ incident on $[d]$ , we get a matching with at least $|V_{1}|-d$ edges as required. ∎

Exercise(A) 6.5.

Let $G$ be a bi-partite graph with partitions $V_{1}=\{x_{1},\ldots,x_{m}\}$ and $V_{2}=\{y_{1},\ldots,y_{n}\}.$ Then $G$ has a subgraph $H$ such that $d_{H}(x_{i})=d_{i},d_{H}(y_{j})\leq 1$ , $\forall 1\leq i\leq m$ and $\forall 1\leq j\leq n$ iff for all $S\subset V_{1}$ , we have that $|N(S)|\geq\sum_{x_{i}\in S}d_{i}.$

Definition 6.6 (Factor of a graph ).

Given a graph $G$ , a factor of $G$ is a spanning subgraph. Equivalently, a subgraph $H$ is said to be a factor (of $G$ ) if $V(H)=V(G)$ . An $r$ -factor is a factor that is $r$ -regular.

Thus, $1$ -factors are nothing but perfect matchings.

Theorem 6.7 (Petersen, 1891).

Every regular graph of positive even degree has a $2$ -factor.

Proof.

Let $G$ be any $2k$ -regular graph for $k\geq 1$ . WLOG, let $G$ be connected. Let $v_{1}v_{2}\ldots v_{n}v_{0}$ be the Eulerian circuit in $G$ . Now, we replace each vertex $v$ by two vertices $v^{-},v^{+}$ and the edge $v_{i}v_{i+1}$ by $v_{i}^{-}v_{i+1}^{+}$ . Thus we get a new $k$ -regular graph $G^{\prime}$ . By Exercise 6.3, there is a $1$ -factor in $G^{\prime}$ . Now, by merging the vertices $v^{-},v^{+}$ in $G^{\prime}$ , we get a $2$ -factor in $G$ . ∎

Here is another application of Hall’s marriage theorem.

Definition 6.8.

(System of Distinct Representatives (SDR) ) Let $A_{1},\ldots,A_{n}$ be a collection of sets. A family $\{a_{1},\ldots,a_{n}\}$ is said to be a SDR if $a_{i}$ are all distinct and $a_{i}\in A_{i},1\leq i\leq n$ .

Corollary 6.9.

A collection $A_{1},\ldots,A_{n}$ has a SDR iff for all $I\subset[n]$ , we have that $|\cup_{i\in I}A_{i}|\geq|I|.$

Proof.

Define a bi-partite graph $G$ on $V_{1}=[n]$ and $V_{2}=\cup_{i=1}^{n}A_{i}$ as follows. $i\sim a$ if $a\in A_{i}$ . A complete matching $M$ on $V_{1}$ in $G$ gives a SDR easily. If $(i,a)\in M$ , then set $a_{i}=a$ .

The condition for all $I\subset[n]$ , we have that $|\cup_{i\in I}A_{i}|\geq|I|$ is equivalent to Hall’s condition for the bi-partite graph $G$ and so the proof follows. ∎

Exercise(A) 6.10.

Let $S_{1},\ldots,S_{m}$ be $r$ -element subsets of $[n]$ with $m\leq n$ and each element belongs to exactly $d$ many subsets. Then $S_{1},\ldots,S_{m}$ has a SDR.

There exist some other easy applications of Hall’s theorem - Chvátal-Szemerédi theorem, Birkhoff-von Neumann theorem on on doubly stochastic matrices and Ryser’s theorem on latin rectangles; See [Jukna 2011, Sections 5.1 and 5.2]. We will see the later applications in the next section.