Talk:Hall's marriage theorem

Infinity of S

Is S allowed to be infinite? If so, this should probably be mentioned, and the link to cardinal number provided. AxelBoldt 21:01 Mar 2, 2003 (UTC)

Saying S is "(not necessarily countable)" implies that it may or may not be infinite (since all finite sets are countable). But I don't see any reason to include a link to cardinal number. According to the text, S may have cardinality of any cardinal number (including finite ones). It may also be of size of any ordinal. Should we include references to ordinal numbers too? S is just a set. To say that should be enough--we shouldn't have to say what properties the set could have. Rob 20:09, 5 December 2005 (UTC)[reply]

Paragraph copied from source

It appears that the paragraph

This can also be applied to the problem of Assignment: Given a set of n employees, fill out a list of the jobs each of them would be able to preform. Then, we can give each person a job suited to their abilities if, and only if, for every value of k (1...n), the union of any k of the lists contains at least k jobs.

is copied almost directly from the bottom of page 10 of the first reference. Ah -- by looking at the history it appears that Robert Borgersen has lifted the quoted paragraph from his own work. Is this ok, copyright-wise? Sam nead 19:49, 5 December 2005 (UTC)[reply]

I can't see any problem with me using my own work as a reference. :) But maybe in the future, people will look and see that it was 'copied' from my work, and not notice that I wrote it. Feel free to reword it...or not...whatever. :) Rob 20:09, 5 December 2005 (UTC)[reply]

Wikipedia is not the place to post original research. If you read a proof that Hall's theorem easily implies Menger's theorem then you should cite that proof. Don't cite your own work posted on the web. If you are the first person to prove that Hall's theorem implies Menger's theorem, then that is cool. Go publish in a combinatorics journal. Then cite the journal. Don't cite your own work posted on the web.

I should add that I feel that self-plagiarism is bad form in Wikipedia and very bad form in academia. Don't do it. yours, Sam nead 04:12, 7 December 2005 (UTC)[reply]

I can definately see how referencing yourself can be bad form, but what I've posted was nothing like original research. The paper I did was like a survey of these 7 theorems in combinatorics, and I reference at the end the papers/books I used. For me to copy and paste text that I wrote in a survey to another survey on the same topic (wikipedia can be looked at as a survey), whats wrong with it? Would you still consider it bad form? Maybe should I change it to an 'External Link' rather than a 'Reference'? Like saying 'Here is some info on this topic...here is a link with more info on this topic'. How's that sound? Or maybe I should copy and paste the references as well? Rob 23:48, 9 December 2005 (UTC)[reply]

Question about (*)

While it's true that

$\left\vert \bigcup (T\cup T')\right\vert \geq \left\vert T\cup T'\right\vert$ and $\left\vert \cup T\right\vert \geq \left\vert T\right\vert$

(by assumption), how does that allows us to say that

$\left\vert \bigcup (T\cup T')\right\vert -\left\vert \cup T\right\vert \geq \left\vert T\cup T'\right\vert -\left\vert T\right\vert$

which is used at the end of the proof?

--71.226.232.199 17:24, 14 January 2006 (UTC)[reply]

It's also true that $\left\vert \cup T\right\vert =\left\vert T\right\vert$ --12.72.245.95 13:06, 9 June 2006 (UTC)[reply]

Good point! I've removed the (*).

(128.112.139.195 04:46, 21 December 2006 (UTC))[reply]

The Konig-Egervary theorem

The Konig-Egervary theorem is the same thing as Konig's theorem, or so I thought. Maybe nowadays one name is used for the statement about bipartite graphs and the other for the (trivially equivalent) statement about 0-1 matrices: In a finite matrix (not necessarily square) whose coefficients are all 0 or 1, the minimum number of "lines" (meaning rows or columns, mixtures allowed) sufficient to cover all the 1's, is equal to the maximum number of 1's no two of which are on a common line. —Preceding unsigned comment added by LDH (talk • contribs)

As far as I can tell from a quick Google, K-E refers to the matrix version, but as you say they are very easily equivalent, and the title "Gráfok és mátrixok" of König's 1931 paper suggests that he was well aware of the equivalence. Maybe it's so easy that K-E should be listed as a section in the König's theorem article, and the redlink redirected, rather than making a new article for it? One thing I'm not sure of, though, and would want to include, is who Egervary was and what contribution Egervary made to the problem. —David Eppstein 06:03, 22 February 2007 (UTC)[reply]

I added a page for Jenő Egerváry. Regarding his contribution to the problem, it was to prove a generalization of König's result to weighted graphs. This is described quite in detail in the combinatorial optimization book by Lex Schrijver. I might add this at some later time. –Voidstar

only if

The system says that there's an SDR iff the marriage condition holds. The proof gives the "if" direction, but not the "only if." (Of course the "only if" direction is trivial, but it should be stated!)

Eclecticos 04:40, 1 October 2007 (UTC)[reply]

Equivalence to Max Flow Min Cut

Any reference for why Hall's theorem is equivalent to the Max Flow Min Cut Theorem? The PDF linked to gives no answer. I just know how Hall follows from Max Flow Min Cut, but not the other way round - and in fact, the other way it seems pretty unlikely to me. —Preceding unsigned comment added by 217.233.151.120 (talk) 09:59, 4 October 2007 (UTC)[reply]

I second this comment. I asked for a source in the article. 83.23.210.94 (talk) 16:01, 11 September 2008 (UTC)[reply]

Reference is inaccessible

Gives me a 403. Is there any way to put that source somewhere publicly viewable (or get a different source altogether)?

Junocola (talk) 03:49, 1 May 2008 (UTC)[reply]

I am shocked that my presentation is still here as a reference! I added it years ago now. Looking at it now, it's certainly not written the best, but I have updated the link. I am glad people are still finding it useful...maybe I will update it and write it a little better. Looking back at the conversation I had with people above years ago, I do now realize how silly it was of me to pull words out of my own work and post it here. I would not do that again. :) --Rob (talk) 00:22, 2 June 2008 (UTC)[reply]

Questions

Some paragraphs from the text:

The marriage condition for S is that, for any subcollection T = {T_i } of S, $|\bigcup T_{i}|\geq |T|$ (i.e. the set created by the union of some n elements, which are themselves subsets of M, in S must itself have cardinality of at least n)
- The given number example could be used to demonstrate this condition (as I have problems understanding this condition...:-).
- There is no n in the formula. Is this a common abbreviation?
If we let M_i be the set of men that the i-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a man if and only if the collection of sets {M_i} meets the marriage condition.
- Wouldn't it be better to speak of S_i rather than M_i, as M was defined beforehand differently?

Thanks, --Abdull (talk) 17:57, 3 August 2008 (UTC)[reply]

Perfect matching

Hello, the article currently says this:

Given a bipartite graph G:= (S + T, E) with two equally sized partitions S and T [...] a perfect matching exists if and only if for every subset X of S

\|X\|\leq \|N_{G}(X)\setminus S\|.

In other words every subset X has enough adjacent vertices in T.

I don't understand why the $\setminus S$ is necessary: isn't $N_{G}(X)$ a subset of T, which is disjoint from S? Maybe I'm just reading something incorrectly... Shreevatsa (talk) 20:48, 18 May 2009 (UTC)[reply]

Sorry, you're right. I thought X could include vertices from both sides of the bipartition but that doesn't work. I'll undo my undo. —David Eppstein (talk) 21:17, 18 May 2009 (UTC)[reply]

Ground set

Even knowing the version of Hall's Theorem for perfect matchings in bipartite graphs, I found the opening sentences initially confusing. At the time X and S are mentioned, there's no indication that X and the members of S are drawn from the same ground set. Someone thinking of a more general setting soon finds that the theorem seems hard to apply. Just a consideration. —Preceding unsigned comment added by 68.183.202.19 (talk) 08:05, 13 October 2010 (UTC)[reply]

Problem with "collection of sets"

There is a technical problem with the statement and proof of the theorem. The article starts out by using "collection of sets", which is not a precisely defined notion. Is it a set of sets, as one can find elsewhere, e.g. here http://en.wikibooks.org/wiki/Set_Theory/Sets? If that were the case, the statement of the theorem would be too weak, because multiple members of that collection may actually be identical. Worse still, the proof is actually incorrect if phrased in terms of sets of sets - I'll leave it as an excercise to find out where. But although the word "collection" is used initially, the proof is phrased entirely in terms of sets, i.e. technically speaking wrong although morally fine.

Looking at the mathematical literature shows one way to fix the problem: Replace the "collection" S by a sequence A₁, ..., A_n. That is the standard approach but does not scale well to infinite S. A second alternative is to make S an indexed family of sets A_i with i a member of some index set I. Both A_i and I are simply sets, and I can be infinite. Either fix requires to rewrite the proof, but only notationally.

Nipkow (talk) 08:20, 3 January 2011 (UTC)[reply]

Is there a reason it doesn't work to interpret "collection" as meaning multiset? Using a sequence seems distasteful to me because the extra ordering information in a sequence is superfluous. —David Eppstein (talk) 09:26, 3 January 2011 (UTC)[reply]

Technically, multisets work fine, and sequences are indeed needlessly ordered. The only problem with multisets is notation and meaning. You can refer to multiset for that, but isn't it going to be confusing that you use sets and multisets together (S is a multiset, its elements are sets), with identical notation? This is actually quite subtle. Look at the formula

\left\vert \bigcup T\right\vert =\left\vert T\right\vert

from the proof: in

\vert T\vert

you mean the cardinality of the multiset

T

, but in

\left\vert \bigcup T\right\vert

, the union operator is a union on sets, and thus we are taking the cardinality of a set. Strictly speaking,

\bigcup T

is not even defined on the multiset page because you are not taking the union of multisets but of sets, which took me a moment to realize. Hence my preference would be for an Indexed family.

Another small point: you may want to refer to Halmos and Vaughan in the text, since the proof is theirs. Nipkow (talk) 17:19, 4 January 2011 (UTC)[reply]

Problem with "subset of men"

I think the language that "Each woman would happily marry some subset of the men" is imprecise. It sounds polygamous. I have changed it to make it more precise. —Preceding unsigned comment added by 159.91.213.146 (talk) 14:41, 4 March 2011 (UTC)[reply]

Article flow

The Theorem is stated with respect to SDR's, then the graph theory equivalent is proved, then the graph theory equivalent is stated. Seems like the proof should be changed to SDR proof, or relocated to be after the statement of the graph theory version. — Preceding unsigned comment added by 209.152.45.46 (talk) 03:57, 18 October 2011 (UTC)[reply]

Infinite S?

Although implied in the article and explicitly mentioned on this talk page, I have never seen a reference that states that the result is valid for infinite S. The bipartite graph proof given (out of context ... this does need to be fixed) just omits to mention that the bipartite graphs are finite - which is explicit in the following section. I very much doubt the validity of the result for infinite S without having any reference to the Axiom of Choice. Perhaps there has been a confusion with the variation of the Marriage theorem proved by Marshall Hall, Jr. (of no relation with Philip Hall, except that they were both from ~~Oxford~~ Cambridge University) which permits the individual sets to be infinite, but still only a finite number of them. This variant gives a lower bound on the number of SDR's that a finite family of sets can have. (By a finite family of sets I mean a "collection" of sets which may have repeats, but having only a finite number of sets when counted with multiplicity). If I am wrong about this please provide a reference. Thanks. Bill Cherowitzo (talk) 05:08, 12 January 2012 (UTC)[reply]

Upon closer examination of Marshall Hall's work, it is clear that my comments above are incorrect. S may be infinite provided the individual sets are finite as the current lead states. I will provide the reference. Bill Cherowitzo (talk) 17:30, 21 January 2012 (UTC)[reply]

S C X

In the proof it says "|N(S)| ≥ |S| for all S C X". Is the "C" a subset symbol? I.e. $|N(S)|\geq |S|{\text{ for all }}S\subset X$ ?--Rumping (talk) 07:47, 20 January 2012 (UTC)[reply]

One might consider reverting this anonymous rewrite, or at least using the old text as a guide. JackSchmidt (talk) 17:12, 20 January 2012 (UTC)[reply]

I am intending on rewriting and reorganizing parts of this page(probably this weekend) and will take care of that little problem. I'll also add a section on Marshall Hall's variant which gives a lower bound on the number of SDR's that are present. And, while I'm at it, I will also fix the lead to be consistent with the references I provide, unless I hear an objection to my comment in the above section. Bill Cherowitzo (talk) 17:44, 20 January 2012 (UTC)[reply]

Something is not right in "Proof of the graph theoretic version hard way"

It is stated that, "On the other hand, NG(W) ⊆ Z: let v in Y be connected to a vertex w in W. The edge (w,v) must be in M, otherwise u reaches w via an alternating path not containing v, and we could take this alternating path ending in w and extend it with v, getting an augmenting path (which would again contradict the maximality of M)." But extending the path with (w,v) doesn't necessarily make it augmenting, as v may not be unmatched.

Using a vertex not in M to extend alternating path

I discovered a similar issue to the section above, I think: in the hard direction of the graph-theoretic proof, we try to show that the entire neighbourhood of a certain w reachable through alternating paths from u is inside Z (the vertices in the right-hand set reached by an alternating path). For the one vertex z = M(w), this is obviously true. But for other vertices v in w's neighbourhood, it says: "If the edge (w,v) is not in M, then one can use it to extend any alternating path that goes from u to w. In either case, v is visited by some alternating path (...)" This would mean that there exists another vertex w2 in W for which v = M(w2), since the path must end in the left-hand set and alternate. What is the proof that all neighbours of w are in M's range? Without this, the proof is broken. --MewTheEditor (talk) 15:49, 4 June 2022 (UTC)[reply]

The definition of alternating paths does not require that "path must end in the left-hand set". That is a consequence of an earlier inference within the proof, not part of the definition. So your objection, that this new edge would contradict a requirement, is bogus because it is not a requirement. —David Eppstein (talk) 23:30, 4 June 2022 (UTC)[reply]

I don't understand how that earlier inference is not useful. In particular: according to what you're saying, would the resulting path (extending u ->* w with the edge w -> v and stopping there) not be an augmenting path (since, as the earlier result shows, we can toggle "M" to "not M" on that path), violating maximality of the matching? --MewTheEditor (talk) 00:56, 5 June 2022 (UTC)[reply]

An ALTERNATING path is one that swaps between matched and unmatched. An AUGMENTING path is an alternating path that starts and ends with an unmatched vertex. They are not the same. —David Eppstein (talk) 01:02, 5 June 2022 (UTC)[reply]

The quote I gave is literally "If the edge (w,v) is not in M, then one can use it to extend any alternating path that goes from u to w. In either case, v is visited by some alternating path (...)". The proof previously shows that an alternating path that starts on the left side and ends on the right side violates the maximality of M. You now claim that it is perfectly fine to construct an alternating path from u (left) to v (right) with as its last edge (w,v). I don't see how this doesn't jeopardise the maximality of M. --MewTheEditor (talk) 09:19, 5 June 2022 (UTC)[reply]

Because the augmenting paths are the ones that jeopardize maximality, not the alternating paths. A maximal alternating path that ends on the wrong side is augmenting. An alternating path that ends on the wrong side but is not maximal (can be extended again later) is not. —David Eppstein (talk) 16:42, 5 June 2022 (UTC)[reply]

Yes, I know, which is the whole point I am making: you say "can be extended again later", and I say that you should prove that this extension is always possible. We have an alternating path from u to w, which looks something like (u,z1,w1,z2,w2,...,w). Now we take a v in w's neighbourhood and extend this path: (u,z1,w1,z2,w2,...,w,v). Unless there exists a w3 such that M(w3) = v, you can now no longer extend this alternating path. That makes it a maximal alternating path. That makes it an augmenting path. That makes it a problem. By contradiction, that means you can always extend from v to some w3 for which M(w3) = v. But who says M's range comprises all the neighbours of w? The right-hand side is perfectly capable of having vertices that are not mapped to by M. What if such a vertex is in w's neighbourhood? Then there is no w3. Then you have a problem. --MewTheEditor (talk) 21:00, 5 June 2022 (UTC)[reply]

If the edge exists, the alternating path can be extended. Period. Whether w3 exists (making it non-maximal) or whether w3 doesn't exist (proved impossible earlier in the proof) is irrelevant at this step of the proof. We don't need to know whether the extended path is maximal to know that it is an extended path. —David Eppstein (talk) 21:11, 5 June 2022 (UTC)[reply]

Application to a standard deck of cards

After the example with the standard deck of cards, the page says: more generally, any regular bipartite graph has a matching. But is this "more general"? Isn't the graph in the deck of cards example not necessarily regular? Samuel Coskey (talk) 19:04, 17 April 2023 (UTC)[reply]