 Solution

ID: past-exam-of-the-probability-statistics-and-options-ii-course-of-the-university-of-oxford/2009/r/r2/iii/solution

Form a bipartite graph with left labels

1, \dots, m

, right set

E

, and an edge

i - e

exactly when

e \in S_{i}

. A matching covering all left labels is precisely a choice of distinct representatives. Its neighborhood condition is

i \in I ⋃ S_{i} \geq ∣ I ∣ for every I \subseteq {1, \dots, m} .

Thus this is necessary and sufficient. The underlying set

E

may be infinite; only the number of sets to be represented is finite.

 New to topics? Read the docs here!