Return to Answer

2 capitalization

There is a direct connection between Hall's marriage theorem (combinatorics) and Linear programming (linear inequalities). Of course, the latter is about finite dimensions, but prominently features duality and convexity, two important tools in functional analysis.

To elaborate on Hall's marriage theorem, consider the following picture:

The dots on the left represent men, the dots on the right represent women and the connecting lines indicate whether this man and woman like each other. The question is whether it is possible to arrange simultaneous, monogamous marriages such that everyone marries someone he or she likes. Hall's theorem gives a necessary and sufficient condition for that: for every subset $M$ of men, the set $$W = \lbrace w \text{ woman}\ |\ w \text{ likes } m, m\in M\rbrace$$ of women liked by these men must fulfill $|M| \le |W|$.

This problem is also known as perfect Matching matching in a bipartite graph. It turns out that it is equivalent to a maximum flow problem, for which we have the min-cut max-flow theorem, which is equivalent to the duality theorem for linear programming. The details of this equivalence are not very difficult and can be found here: http://web.mit.edu/k_lai/www/6.046/r11-handout.pdf .

Unfortunately, I haven't found a ready-made proof of Hall's theorem from the duality theorem, you'd have to work that out yourself for your lecture. The intermediate reformulations are bit long, I don't think it's worth spending more than a cursory remark on them; I'd jump right to the reformulation as linear program.

1

There is a direct connection between Hall's marriage theorem (combinatorics) and Linear programming (linear inequalities). Of course, the latter is about finite dimensions, but prominently features duality and convexity, two important tools in functional analysis.

To elaborate on Hall's marriage theorem, consider the following picture:

The dots on the left represent men, the dots on the right represent women and the connecting lines indicate whether this man and woman like each other. The question is whether it is possible to arrange simultaneous, monogamous marriages such that everyone marries someone he or she likes. Hall's theorem gives a necessary and sufficient condition for that: for every subset $M$ of men, the set $$W = \lbrace w \text{ woman}\ |\ w \text{ likes } m, m\in M\rbrace$$ of women liked by these men must fulfill $|M| \le |W|$.

This problem is also known as perfect Matching in a bipartite graph. It turns out that it is equivalent to a maximum flow problem, for which we have the min-cut max-flow theorem, which is equivalent to the duality theorem for linear programming. The details of this equivalence are not very difficult and can be found here: http://web.mit.edu/k_lai/www/6.046/r11-handout.pdf .

Unfortunately, I haven't found a ready-made proof of Hall's theorem from the duality theorem, you'd have to work that out yourself for your lecture. The intermediate reformulations are bit long, I don't think it's worth spending more than a cursory remark on them; I'd jump right to the reformulation as linear program.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9579049944877625, "perplexity_flag": "head"}