2
$\begingroup$

Still another exercise on Reinhard Diestel Graph Theory, GTM 173, edition 3 (on page 51)

Let $A$ be a finite set with subsets $A_1, \cdots, A_n$, and let $d_1, \cdots, d_n \in \mathbb N$. Show that there are disjoint subsets $D_k \subseteq A_k$, with $|D_k| =d_k$ for all $k \leq n$, if and only if $|\cup_{i\in I}A_i| \geq \sum_{i \in I} d_i$ for all $I \subseteq \{ 1,\cdots,n\}$.

This "if and only if" statement is clear in one direction since for the properly chosen $D_k$, $|\cup_{i\in I}A_i| \geq |\cup_{i\in I}D_i| = \sum_{i \in I} d_i$. But the proof of the other direction seems more complicated to me. I tried to prove it by induction, but failed.

Since I am a beginner of graph theory, I just take it as an exercise of set theory, and cannot think it in the way of graphs. Maybe graph theoretic methods are favorable. Longing for your advice. Thanks very much.

2 Answers 2

3

This is a slight generalization of the finite case of Hall's marriage theorem.

If your textbook is the same one I found a PDF of online, Hall's theorem is theorem 2.1.2 on page 36, so effectively the exercise is just to see how your problem can be formulated as an instance of the marriage theorem.

Hint: First consider what the problem looks like if all $d_i$ are $1$.

  • 0
    I understand it now. By properly constructing a bipartite graph and using the marriage theorem to find a matching, I can finally find the set $D_k$ in need. Thus this problem, seemingly related only to sets can find a nice solution. Thanks a lot for your answer. I find graph theory more fascinating now :)2012-09-24
1

If such $D_k$'s exist, then for all I, $|\bigcup_{i\in I}A_i|\geq \sum_{i\in I}d_i$. Conversely, suppose $|\bigcup_{i\in I}A_i|\geq \sum_{i\in I}d_i$ for all I. Construct a bipartite graph G with bipartition (B1, B2) such that $B_1$ consists of $d_1$ copies of $A_1$, $d_2$ copies of $A_2$, ..., $d_k$ copies of $A_k$, and $B_2 = A$. Let $U\in B_1$ be adjacent to $v\in B_2$ if $v\in U$. Now consider $X\subseteq B_1$. Let J be the set of indices of $A_j$'s that appear (in any number of copies) in X. Then $|X| \leq \sum_{j\in J}d_j \leq |\bigcup_{j\in J}A_j| = |N(X)|$. Hence by Hall's Theorem there is a complete matching M of $B_1$ in G. Define $D_i = \{u\in B_2 : u$ is matched with $A_i$ in M}.