Answer to Question #254864 in Discrete Mathematics for Unknown354520

Question

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

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 =13 $[b, e, i, l, a, j, m, c, f, k, h, d, g]$

Total no. of sub sets =13

Hence,

System of distinct representatives,

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