• Support PF! Buy your school textbooks, materials and every day products Here!

Marriage problem

  • Thread starter Pietjuh
  • Start date
76
0
I'm supposed to show that the marriage problem has a solution if every man is friends with exactly r women, and every women is friends with exactly r men.

I rewrote this problem in the language of transversals. I defined sets
[tex]S_i = \{ j | (i,j) \in E \}[/tex] in which E is the set of branches of the bipartite graph of the problem. It's obvious that every set [tex]S_i[/tex] has exactly r elements and that every element in {1,...,n} appears exactly r times in the collection of all these sets. To show that the mariage problem has a solution I must show that the collection [tex](S_1,S_2,\cdots,S_n)[/tex] is a transversal. And this is where I get stuck! :( Or is it really just so simple that it is too simple to see the solution? :uhh:
 

Answers and Replies

208
0
I think you need to take the negative of the woman and add it to the positve of the man and then intergate it with the limits of logic
 
1,675
3
mathmike said:
I think you need to take the negative of the woman and add it to the positve of the man and then intergate it with the limits of logic
I fear the result will be complex .

Jokes aside, please state the entire marriage problem for those of us
who aren't familiar with it.
 
76
0
Ok here's the explanation of the marriage theorem:
Let's say we've got a bipartite graph G = (V,E) in which V = V_1 U V_2
The vertices in V_1 are called men, and those in V_2 are called women.
The marriage problem is the problem of finding a complete matching in this bipartite graph. So you need to match every man with every women, such that no man or woman is matched more than 1 time.

The marriage theorem of Hall says this problem has a solution if for every k-tuple of men, the number of women they are willing to have a relationship with is larger or equal than k.

So in my problem you don't have a problem if k <= r, because if you take a k-tuple with k<=r the number of people they are willing to have a relationship with is at least r >=k. All I need to show is that for every k-tuple with k > r you can always find at least k friends.
 
1,675
3
I think I'm missing something. You can match everyone (and trivially) if and only if
the number of men is equal to the number of women. No?
 
Top