Guichard-Combinatorics-Graph-Theory · Problem 4.1.4

Systems of Distinct Representatives

Mathematics — Probability · systems-of-distinct-representatives

Problem

Suppose the set system

A_1, A_2, \ldots, A_n

satisfies

|\bigcup_{j=1}^{k} A_{i_j}| \geq k + 1

for every

1 \leq k < n

and

\{i_1, i_2, \ldots, i_k\} \subseteq [n]

, and that

x \in A_i

. Show the set system has an SDR in which

x

represents

A_i