🚀 go-pugleaf

Howard S Shubs wrote:

> In article <33E3CEBA.2DDFA622@dspse.com>, Ashok Ramasubramanian
> <ashok@dspse.com> wrote:
>
> >Howard S Shubs wrote:
> >>
> >> I've heard it said that there's someone for everyone, but I've
> never seen
> >> a proof of it.  Is there a mathematically-oriented person here who
> would
> >> like to try it?  Here, I'll help:

[snip!]

> >Now for the mathematics....

[snip!]

> Not exactly a rigorous proof, sir, I think.
>
> If the set of "All Available Women" is set W, and the equivalent male
> set
> is set M, and I want to show bidirectionally that for every member of
> M
> there is at least one member of W, I can make a disproof by showing a
> member of either set who has no match in the other set.  (I like
> sets.)
>
> I'm a callin' in the pros, here.  I added sci.logic to the Newsgroup
> list.  Assuming that they don't consider this inappropriate, perhaps
> they'd be willing to give it a shot.  Or maybe they'd be willing to
> tell
> me of a group which would be more appropriate than logic.  Honest,
> this
> isn't an attempt to add noise to your group!

In fact, there is a result known as "Konig's Marriage Theorem" in
mathematics,
and what it says is this.  We are given two sets   W (women)   and  M
(men).    Each
woman is willing to marry some of the men, and conversely each man is
willing to
marry some of the women.  Let's say that a woman  w  and a man  m  are 
"compatible"
if they are willing to marry each other.  The question is, when is it
possible for all of
the women to marry men with whom they are compatible?  One necessary 
condition
is as follows: for every subset  S  of the set of all women, the set
M(S) of men who are
compatible with some woman in S must be at least as large as S.   The
reason is clear...
each woman in S must be paired with a man in M(S).  Konig's theorem is
that when
this condition is satisfied it is possible for all of the women to
marry.

So, in short, the statement that "there is someone for everyone" is most
likely true,
but whether or not everyone can be paired up compatibly is another
question.

Finally, I'd like to remark on the implicit heterocentricity of the
previous postings...
for many people, the "someone" for them is not of the opposite sex.  If
you take this
into account you will have to apply "Tutte's One-factor Theorem"
instead, for which
I refer you to any introductory textbook on graph theory.

I suspect that this doesn't really address the real issues of your
conversation, but,
well, you asked...

Cheers!
Dave Wagner