Guichard-Combinatorics-Graph-Theory · Problem 4.1.3

Systems of Distinct Representatives

Mathematics — Probability · systems-of-distinct-representatives

Problem

Suppose the set system A1,A2,…,AnA_1, A_2, \ldots, A_n has an SDR, and that x∈Aix \in A_i. Show the set system has an SDR containing xx. Show that xx cannot necessarily be chosen to represent AiA_i.

Browse the problem library