How to argue that an $A$-covering matching exists in this bipartite graph?

Question

In lecture the following was mentioned in the context of matchings in bipartite graphs:

Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$. For $u \in U$ let $r(u) := \lvert \{S \in \mathcal{S} \mid u \in S\}\rvert$ and let $n := \lvert \mathcal{S} \rvert$ and $N := \sum_{S \in \mathcal{S}} \lvert S \rvert = \sum_{u \in U}r(u)$. Assume that $\lvert S \rvert < \frac{N}{n-1}$ for all $S \in \mathcal{S}$ and $r(u) < \frac{N}{n-1}$ for all $u \in U$. Then there exists an injective function $f: \mathcal{S} \rightarrow U$ with $f(S) \in S$ for all $S \in \mathcal{S}$.

I recognise that we can represent this as a the problem of finding an $\mathcal{S}$-covering matching in the bipartite graph $G(V,E)$ with $V(G) = \mathcal{S} \uplus U$ and $E(G) := \{ \{u,S\} \mid u \in U, S \in \mathcal{S}, u \in S \}$. Now I tried induction over $n$. The induction basis is clear, so let us assume as induction hypothesis that there exists a matching covering all of $\mathcal{S}$ for $\lvert \mathcal{S} \rvert = n$. Now to the induction step. We assume that $\lvert \mathcal{S} \rvert = n+1$. In case that $S_{k+1} \not\subset \cup_{i=1}^kS_k$ the claim is clear since there exists one $u \in U,S_{k+1}$ that is not yet matched. But I do not know what to do with the case $S_{k+1} \subset \cup_{i=1}^kS_k$. I suppose that we somehow need to apply the assumption $\lvert S_i \rvert < \frac{N}{n-1}$ for all $S_i \in \mathcal{S}$ here, but I do not see how. Could you please give me a hint?

Answer 1

The inequality $|S| < \frac{N}{n-1}$ indeed is very important. Suppose $\mathcal{S} = \{S_1, S_2, …, S_n\}$, where $|S_1| \leqslant |S_2| \leqslant … \leqslant |S_n| < \frac{N}{n-1}$.

• First, $N = \sum\limits_{S\in \mathcal{S}}|S| = |S_1| + \sum\limits_{i=2}^n|S_i| \leqslant |S_1| + (n-1)|S_n| \leqslant |S_1| + (n-1)\left(\frac{N}{n-1}-1\right)$.

  That means that for all $i\in \{1, …, n\}$, $|S_i|\geqslant|S_1| \geqslant n-1$.

• Now we will use Hall's theorem to prove the result. Suppose $X\subseteq\mathcal{S}$ and distinguish:

  • if $|X| = 0$, then $|N(X)| = 0 \geqslant |X|$;
  • if $1\leqslant |X| \leqslant n-1$, then since $X$ is not empty, it means it contains a certain $S_i$, and using the previous inequality, $|N(X)| \geqslant |S_i| \geqslant n-1\geqslant |X|$;
  • if $|X| = n$, then $X = \mathcal{S}$. If $|N(X)| < |X|$, that means that $|N(X)| = n-1$ and that $S_1 = S_2 = … = S_n$ (all subsets have the same $n-1$ elements $u$). If thats the case, that means that for all $u\in S_i$, $r(u) = n = \frac{N}{n-1}$, which is not possible given the inequality $r(u) < \frac{N}{n-1}$.

  In all cases, we proved that $|X| \leqslant |N(X)|$. Using Hall's theorem, there exists a matching covering $\mathcal{S}$, which proves the wanted property.