Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
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 :) –  ShinyaSakai Sep 24 '12 at 7:22
add comment

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}.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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