Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Marriage problem

  1. Jul 27, 2005 #1
    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:
  2. jcsd
  3. Jul 27, 2005 #2
    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
  4. Jul 27, 2005 #3
    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.
  5. Jul 28, 2005 #4
    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.
  6. Aug 2, 2005 #5
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook