Combinatorics and Graph Theory · Problem 4.1.3

Systems of Distinct Representatives — David Guichard

Mathematics — Combinatorics · 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