Marriage problem

  • Thread starter Pietjuh
  • Start date
  • #1
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

  • #2
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
 
  • #3
1,681
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.
 
  • #4
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.
 
  • #5
1,681
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?
 

Related Threads on Marriage problem

  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
3
Views
740
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
6K
Replies
7
Views
5K
  • Last Post
Replies
3
Views
820
Replies
2
Views
5K
Replies
13
Views
4K
Replies
16
Views
4K
Top