currently at it working on my discrete mathematics assignment, where I now have one assignment, that I just can't crack. I feel like I am very close, but miss something critical to it.
So, I have the following game: X = {x_1, x_2, ... , x_n}, called spaces. Now we have a set of sets called W_1, ... , W_m that are all subsets of X, called winning sets.
Now, two players take turns taking out one element from X. Once the element from X is taken out, the other player cannot choose it anymore.
The first player to choose all the elements from X that make up any set W wins.
In this way, tic-tac-toe is a game with X = {x_1, ... , x_9}, where the W describe all the diagonal, horizontal and vertical lines in a 3x3 field.
The game I am looking at right now works with the following rules: Any set W must have |W| >= 10. No x from X may be part of more than 5 sets W.
I have the following tips: I should show, that there is a family of disjoint pairs of spaces in X, so that in every W there is one of these disjoint pairs. I should make a graph to help that is bipartite, using X with W as it's set of nodes.
Now, the first part of this longer assignment was to show, that in a bipartite graph G(S with T,E) that satisfies the polgamy-marriage condition, that is, |N(A)| >= 2*|A|, for every A that is a subset of S, that we can construct a family of disjoint K_1,2 graphs, which have all the nodes in S as their "middle" node.
I understand how showing the pairs that are in all the winning sets would allow player 2 to always cause a draw, and I understand, that if I could show how to make the constructed graph G(X with W,E) into a Graph that satisfies the polygamy-marriage condition, I could find these pairs, but I don't know how to make that step. The only place I see a 2 popping up here is by the fact, that 10/5 = 2, but I tried doing anything there and haven't found how to make that plausible here.
I would be very glad about any tips anyone could give me. I feel like I am just missing something obvious here.
Thanks for reading!
So, if I understood you correctly, you have some family of subsets of $X$ s.t. any subset contains at least $10$ elements and every element is member of at most $5$ subsets. You want to show that biparite graph with subsets from the family as left part and $X$ as right, with edges from subsets to elements in this subsets, satisfies polygamy-marriage condition. Is it so?
If it is, it's pretty straightforward. Take any family $F$ of subsets. There are at least $10|F|$ edges incident with $F$ (as any subset is incident to at least $10$ edges). But as every space is incident to at most $5$ edges, there are at least $\frac{10|F|}{5} = 2|F|$ spaces incident to this edges - ie neighbors of $F$.