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

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?

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.