Combinatorics and Graph Theory · Problem 4.1.4

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 satisfies ∣⋃j=1kAij∣≥k+1|\bigcup_{j=1}^{k} A_{i_j}| \geq k+1 for every 1≤k<n1 \leq k < n and {i1,i2,…,ik}⊆[n]\{i_1, i_2, \ldots, i_k\} \subseteq [n], and that x∈Aix \in A_i. Show the set system has an SDR in which xx represents AiA_i.

Browse the problem library