Proof: Hall's Marriage Theorem for Bipartite Matchings | Graph Theory
ฝัง
- เผยแพร่เมื่อ 4 มี.ค. 2020
- A bipartite graph G with partite sets U and W, where |U| is less than or equal to |W|, contains a matching of cardinality |U|, as in, a matching that covers U, if and only if for every subset S of U, |S| is less than or equal to the cardinality of the neighborhood of S (as in - S has as many or fewer vertices than it has neighbors). This is Hall's theorem for bipartite matchings, also called Hall's marriage theorem. We prove the theorem in today's video graph theory lesson!
The first direction of the proof is a breeze! Then we use strong induction and cases to prove the other direction! It's a lot of fun!
Lesson on Hall's theorem and Hall's condition: • Hall's Theorem and Con...
Lesson on matchings: • Matchings, Perfect Mat...
Lesson on vertex-induced subgraphs: • What is a Vertex Induc...
I think those are all the links I promised in the lesson. Let me know if I missed one!
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
You're killing it with the proofs man! Don't ever stop what you do!
Thanks, Matthew! I'm not gonna stop until I kick the bucket, new lessons every 2 days!
Wow you present everything so intuitively, you're an excellent teacher !
Thanks so much, I am glad it was clear and thanks for watching!
This channel is fantastic, I've been making my way through all of these videos slowly over my degree and they're incredibly useful.
Thanks so much! If you're using the graph theory playlist and haven't already realized, here is my warning that it is not in any particular order! It starts off seeming like it is in a reasonable order, but that stops after 50 lessons or so I think. I hope they continue to be useful and let me know if you ever have any questions! One day I am gonna make that playlist just the way it should be!
Out of curiosity, what was/is your degree?
Thank you very much! I've been struggling to understand the proof of Hall's theorem in class and you made it much easier to follow! I appreciate the signposts where you do a quick preview of what's to come in the intermediate steps of the proof.
You're very welcome, Kathy! I am so glad you found the lesson helpful, this one was a lot of work - and definitely one of my favorites! If you want a break from the long graph theory proofs, consider checking out my math raps! th-cam.com/play/PLztBpqftvzxW7a66b0dJPgknWsfbFQP-c.html
You're a lifesaver, thank you so much!
You're welcome!
Amazing, amazing, amazing. Your proofs are so crystal-clear. Thank you for not trying to make things look 'simple' by glossing over the thorny details as many educational videos tend to do. The way you talk through everything you're doing makes the subject so much more intuitive. Thank you.
Thanks so much for the kind words, Ilona! Let me know if you ever have any questions!
Thank you so much for presenting everything!!
is it possible for you to also do one video on stable matching / the gale shaply algorithm?
I love this channel. Keep posting and keep adding to this wonderful archive. If you keep doing this, then this will potentially become the best no BS math channel on the internet (minus KhanAcademy but they only cover easy stuff)...then all the ppl that presumably made fun of you in High school will FEEL THE WRATH!!!
He made a video reply to this haha instagram.com/p/CGvpztdAzO9/?
@Kavin Fan You just outed me before I was able to give my actual reply to this comment 😂
@S G Thanks so much! I will keep doing it as long as I possibly can, and your last remark about all the people who made fun of me in high school I found highly amusing, Kavin Fan provided the link to my Instagram video about it haha. THEY WILL ALL FEEL THE WRATH!
I read the proof from Kenneth Rosen's book, but I don't have any ways to wrap my head around. This is actually a ton of helps.
Yes, Definitely the best video on youtube on this proof.Thanks, bro Thanks a lot
So glad you found it useful! You're very welcome and thanks so much for watching!
Truly beautiful 🎉 enjoyed every moment thank you for the complete proof
Glad to help, thanks so much for watching!
Very helpful. Brilliant explanation
Thank so much!
Brilliant, man. Literally wasted 2 hours cause I wasn't really getting the proof when I should've just watched this. TH-cam promptly showed me your video first as it was the most popular.
Thank you very much for watching and for the kind words! I respect your 2 hours of effort to understand the proof, and am glad this lesson could help clear up the details!
Excellent take Mr. Really a helpful video with such a lucid explanation. You made the theorem worth learning
So glad to hear it, thanks for watching, Riya! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath Definitely. Your explanation helped me to carve out the problem statement formulation for my Ph.D. work. Thanks again
Hi, this video was quit useful! Could you please consider on doing proofs for "Least Squares Approximation" ? Thank you and very well explained!!
Hi, the way you explained is amazing, can you please upload a video for Konig's theorem and Tutte-Berge for non-bipartite matching.
It would be really great as I have an exam next week.
Incredibly nice video, thanks a lot for your clear explanation, just a little question about the understanding of the structure of the graph , since the subgraph H is generated by deleting just pair of vertices u and w, can I interpret that the U-x has just 1 single vertex u, so that subset x' has only 1 single vertex u as well? Esentially the only difference between H and G is the two vertices u and w? Thanks in advance !
Very well explained!
Thank you! I am glad it was clear!
You are the best! Don't stop creating such invaluable content for fascinating subjects such as Graph Theory. Can I send over a past examination question which I am struggling on? I think it would make for a good video entailing Systems of Repenstivies and Halls Theorem.
Again, thank you for such inspiring teachings.
Thanks a lot for watching and for your kind words, Avi! Please do share the question and I'll consider making a video about it! I can never make any promises in that regard, but I'm always happy to hear problems people are thinking about! You can share it here, or if a different method is preferable you can email me at wrathofmathlessons@gmail.com, or message me on Instagram or Facebook (links to those profiles are in the description). Thanks again!
What a great video, I'm learning graph theory for my undergraduate thesis, but I have some problem with paired domination number and upper bound on paired domination number(the gamma of upper bound and gamma the minimum cardinality). I could not get the exact example cause lack of journal that explain and give the example of them. Would you mind if you make a explanation video about these problem? thankyou
amazing❤
this is brilliant! thanks!
Thanks, Nawar! This has been one of my favorite lessons since I made it. Long proofs like this are a lot of fun!
i couldn't understand the proof in wikipedia. I understood this pretty easily! Thanks a lot!!!!!
Glad to help, thanks for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Bipartite matchings? More like "Beautiful lectures; keep going!" 👍
Thanks a lot
Back to basics, need to learn about strong induction to understand this proof. Till now my toolset only had weak induction.
Can you recommend reading sources for this proof and the related lessons on matching?
I am a PhD student in economics and this is helpful. Thank you for making this great quality explanation of proof.
Hey man
Doing my Bachelors in math and Computing and am interested in economics can you tell me if these concepts will be really useful if i go deep into economics in the future?
Also keen on knowing where you applied this theorem.
How is the PhD going/how did it go?
@34:53 you gave a billion dollars smile of victory. Just awesome!!!
Thank you! This is one of those lectures I had to rehearse every day for a week so that I had a good chance of getting a good take when I hit record, so it was great to finish it up!
I gotta say, your videos totally crack me up. And they are edumacational. I just want to give you positive feedback, no other agenda here.
Thanks so much, Jim!
Thank you very much!!!
My pleasure, thanks for watching!
Do you know any high problem solvable with Tutte theorem?
@Wrath of Math
Can you make a video on 2 step Laplace transform?
I wish this video was there on TH-cam in 2019 when I had my graph theory paper...couldn't find one then for this proof...anyway I have another paper coming up where I would need this proof again...so thanks for this! Best video out there covering Hall's!
Thanks for watching, I am glad the video is out for you now and am happy to hear you have found it valuable! Let me know if you ever have any video requests!
@@WrathofMath sure sir, probably more on things like number theory
Thanks dude!
My pleasure, thanks for watching!
I have a doubt if X'
Could we have another constructive proof? I am not sure whether my logic is correct. If you can confirm, that would be great. What if the very first time when we choose the vertex at the induction step, we choose a vertex that has the minimum number of neighbors and then induce the graph that remains after deleting that vertex and the edges connected to that vertex. Would not we get an induced graph in which Hall's condition is guaranteed? Then we could, of course, use the induction hypothesis to finally prove the theorem.
This wouldn't work because the neighbors of that vertex could have been neighbors of other vertices in G. Imagine a second vertex in G that had the same neighbors as the first. Then that vertex would be left with zero neighbors!
kindly upload a video on Mader theorem and konig's theoem.
you are genious. Your lecures are just amazing...
Thank you so much! Right now I'm having a scientific initiation ( it started last week) and choose graph theory for it, your proofs and explanations are helping me a lot.
Anyway, heres a quick doubt I had while you were doing your proof: I don't get case 2 at all. How can it be possible? By strong induction you have every |U|
Thanks for watching, Joao! I'm glad to hear my lessons have been helpful. That's a great question, there's a small detail you're missing that is causing the confusion. I could have helped by writing more on the board, but I try not to write too much on it because it's small haha! The induction proof is to prove that if a bipartite graph satisfies Hall's condition, then it has a matching covering the smaller partite set. So our induction hypothesis was not to assume when |U|
@@WrathofMath thank u so much for this explanation my, now I've got everything I needed to cope with the proof! Be well!
Kindly, do some little work on the following topics
1. Dual Graphs
2. Infinite Graphs
3. Colouring of vertices, faces and edges in Graphs
Thank you😊
this explanation is too long🥲
Just gonna make sure the words make sense to me:
Hall’s Theorem says that every subset of the smaller(or equal) partition of a bipartite graph has a neighborhood at least as big as itself, and that if that condition is satisfied there is a matching that covers all of the vertices in the smaller partition.
Case 2:
H is a subset of G so if H doesn't satisfy hall's condition then that means that there is subset H in G which doesn't satisfy hall's condition. But we assumed in the beginging that G satisfy hall's condition in both cases. Plz answer
H is the entire *graph* (not just a subset of U) you get after removing one vertex from G and removing one of that vertex's neighbors from G. Some of the vertices in H could have depended on the neighbor that was removed, so H does not necessarily satisfy Hall's condition. The vertex _u_ had an edge connecting it to one of its neighbors _w_ . Consider a vertex in H called _z_ (which is also in G). What if _z_ only had one neighbor in G which was _w_ ? Then removing _w_ would have caused _z_ to have zero neighbors, violating Hall's condition.
Wonderful
Thank you!
@@WrathofMath really loved the joy you had when you finally got the proof done, hope you get more and more views
This was an amazing proof. I could understand everything around Hall's theorem and why the particular step happened in one go, and that speaks volumes about the quality of your delivery. Thank you very much.
@Wrath of Math. Please do a video on min max theorem.
Thanks for watching! What min-max theorem in particular do you mean?
@@WrathofMath max flow min cut theorem in network flow
good but a little hard to pay attention, you say the same thing quite too often. Could be way more precise and simple.
🐐🐐🐐
The proof starts at 8:40 (At least for the not trivial part lmao)
It’s where the warm up ends haha
awesome...
DinBP ki MKC
Thanks for watching!
Too lengthy.
If the video is too long I'd recommend just reading a proof of the theorem. If you need some more in depth explanation the video is here for you! I tried to explain every step very carefully in this lesson.
one take shawty
I don't want a lover I'm allergic to subsets of cartesian products
Edit: Sidenote, I rehearsed this proof every night for a week in order to get this take, quite the challenge!
Haha, I had to do the same one for my class, my board doesn't flip like yours though.