1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.