TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 34

Reformulate the exercise as graph theoretical problem:

Given a set $A$ with $n$ elements and $B = {A_{1}, A_{2}, ..., A_{n}} \subseteq 2^{A}$ . Prove that there exists an injective mapping $f : B \to A$ such that $f (A_{i}) \in A_{i}$ for all $i \in {1, 2, ..., n}$ if and only if for all $I \subseteq {1, 2, ..., n}$ the cardinality of $⋃_{i \in I} A_{i}$ is at least equal to the cardinality of $I$ .

Solution

We construct a bipartite graph by placing a node for every set $A_{i}$ on the left side. Then we place a node for every element of $A$ on the right side. We connect a node for a certain set $A_{i}$ with every node which contains an element of $A_{i}$ with an undirected edge. To get an injective mapping we need to select a complete matching. This is the same task as in the marriage theorem. The elements of the set $A$ represent the men, while $A_{i}$ represents the set that woman $i$ is willing to marry. So to get to a complete matching all unions of the form $⋃_{i \in I} A_{i}$ must be greater or equal to the number of sets in the union $I$ .

Comment: This has to be proven here, doesn't it? Selfanswering (for other people): No, it hasn't. The iff-part in the description of this exercise refers exactly to the marriage theorem, so this is correct.

To make things clearer we give a small example where we can construct an injective mapping:

$A = {1, 2, 3}$

$B = {A_{1}, A_{2}, A_{3}} \subseteq 2^{A} e.g. B = {{1}, {1, 2}, {2, 3},}$