System of Distinct Representatives

[JJ6]

Homework Statement

I have the following graph theory problem:

Homework Equations

The only theorem I know about SDRs is Hall's theorem:

Let S_1, ... , S_k be finite sets. S_1, ... , S_k has an SDR if and only if the union of any n of the sets has at least n elements.

The Attempt at a Solution

I have no idea how to start. The only theorem we've gone over in class dealing with SDRs is Hall's, but I have no idea how to apply that.

 

[mighty2000]

Dear student,

Thank you for sharing your graph theory problem with us. It is great that you are familiar with Hall's theorem, as it is a very useful tool for solving problems involving SDRs.

To start, let's break down the problem and see what information we are given. From the statement of the problem, we can see that we are dealing with a finite number of sets, which we can label as S_1, S_2, ..., S_k. Furthermore, we know that the union of any n of these sets has at least n elements.

Now, let's think about how we can use this information to find the solution. Hall's theorem tells us that for a set of sets to have a System of Distinct Representatives (SDR), the union of any n of the sets must have at least n elements. This means that if we can prove that the union of any n of our sets has exactly n elements, then we have found our SDR.

So, our task now is to find a way to construct sets S_1, S_2, ..., S_k such that the union of any n of them has exactly n elements. One way to do this is to create sets with overlapping elements. For example, let's say we have three sets: S_1 = {1, 2}, S_2 = {2, 3}, and S_3 = {1, 3}. The union of any two of these sets will have two elements, and the union of all three will have three elements, giving us a SDR.

You can try this approach with different numbers of sets and elements and see if you can come up with a general solution. Good luck and happy problem solving!