Max-Flow Min-Cut Theorem to Hall

[RK4]

Hi all! I'm trying to use the Max-Flow Min-Cut Theorem to prove Hall's Marriage Theorem. How can this be done? Thanks!

[RK4]

Wow! Seems as if everyone is clueless.

[Dave]

I've never even heard of them

[RK4]

I've never even heard of them

 

Oh really? Wow, that's so interesting!

[matt grime]

Not sure what you were expecting really: the number of mathematicians reading this site is negligible, and the number of those who've done enough optimization to know what max-flow/min-cut is must be, oh, about 3.

 

I can only see two possible networks to construct. One has as vertices all the elements and is complete with the weight of edge i to j the number of subsets i and j lie in, the other is sort of dual: the complete graph on all the subsets with the weight of each edge the cardinality of the intersection.

 

However, it is up to you to figure out what condition 'there is a set if distinct representatives' corresponds to, if anything at all.

[Sisyphus]

Not sure what you were expecting really: the number of mathematicians reading this site is negligible' date=' and the number of those who've done enough optimization to know what max-flow/min-cut is must be, oh, about 3.

 

[/quote']

 

Hey! I'm not a mathematician, but I knew what he was talking about. I just figured my bumbling attempts would be less valuable than what Google would turn up for "Hall's theorem Konig's theorem logical equivalence" or some variation thereof.

[matt grime]

Then you must belong to the (even smaller?) subset of nonmathematicians who read the mathematics threads and who know what max-flow min-cut is. (I imagine lots of computer scientists also know what it is.) However it is a reasonable observation that the number of mathematically minded who read this site is a lot lower than say sci.math, or other places.