Combinatorics Consider the family sets 123234 34 45 125 Find

Combinatorics

Consider the family sets {{1,2,3},{2,3,4}, {3,4}, {4,5}, {1,2,5}}. Find all systems of disinct representatives (SDRs) of the family.

Solution

SDR = System of distinct representatives. Given a finite family of sets X={S1,…,Sn}X={S1,…,Sn}, a system of distinct representatives, or SDR, for the sets in XX is a set of distinct elements x1,…,xnx1,…,xn with xixi belongs to SiSi for 1in1in.

I need to determine whether the families of sets have an SDR or not.

a) {1,2,3},{2,3,4},{3,4,5},{4,5},{1,2,5}{1,2,3},{2,3,4},{3,4,5},{4,5},{1,2,5}

b) {1,2,4},{2,4},{2,3},{1,2,3}{1,2,4},{2,4},{2,3},{1,2,3}

I\'ve been looking for an example that would explicitly show me what happens and explain step by step what to do to find a SDR. Appreciate any explanations.