Answer to Question #254863 in Discrete Mathematics for Unknown354520

Question

Find a system of distinct representatives for the following sets: {a, c, f}, {b, g}, {c, d, h}, {a, d, j}, {e, i, k}, {f, j, l}, {b, i, k}, {e, g}, {a, c, f, h, l}, {g, k}, {b, e, i}, {d, h, j}. 

Answer 1

By Hall's Theorem,

An SDR (System of distinct representatives) is a collection of distinct elements $a_{1}, a_{2}, \ldots a_{m}\ \text{such that}\ a_{i} \in A_{i}\ \text{for}\ i=1,2, \ldots m$

Let $A_{1}, A_{2}, \ldots, A_m$ be subsets of A

$A_{1}, A_{2}, \ldots, A_{m}$ has an SDR if

$\left|\bigcup_{i \in I} A_{i}\right| \geqslant |I|$

In our case

Total no. of distinct elements =12 $[a, c, f, b, g, d, h, j, e, i, k, l]$

Total no. of sub sets =12

Hence,

System of distinct representatives,

$=\left\{a, c, f, b, g, d, h, j, e, i, k, l\right\}$