Hall’s Marriage Theorem and Related Aspects
(2022) In Bachelor's Theses in Mathematical Sciences MATK11 20212Mathematics (Faculty of Engineering)
Mathematics (Faculty of Sciences)
- Abstract
- The main focus of this thesis is to study Hall’s Marriage Theorem, which
was named after, and proven by the English mathematician Philip Hall in 1935
[6]. The theorem can be stated in terms of different mathematical fields and
there are several equivalent theorems proven by other mathematicians [3]. This
thesis is mainly going to focus on the graph-theoretic formulation. When stated
in terms of graph theory, Hall’s Marriage Theorem gives necessary and suffi-
cient conditions for the existence of a special type of edge sets called perfect
matchings. The second half of the thesis is dedicated to the applications of the
theorem, as well as some of its connections to group theory. - Popular Abstract
- Hall’s Marriage Theorem was named after the English mathematician Philip
Hall who proved it in 1935. Although as it turns out, a theorem proven by Karl
Menger in 1927 is equivalent to the one proved by Hall [3]. It answers the
Marriage Problem: ”If there is a finite set of girls, each of whom knows several
boys, under what conditions can all the girls marry the boys in such a way
that each girl marries a boy she knows?”[8, p.112] It was formulated in terms
of set theory rather than the nowadays more common formulations in terms of
combinatorics or graph theory, the latter of which will be the formulation used
in most of this thesis.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9088771
- author
- Eklund, Rasmus LU
- supervisor
- organization
- course
- MATK11 20212
- year
- 2022
- type
- M2 - Bachelor Degree
- subject
- keywords
- Hall's Marriage Theorem, Coset Intersection Graph, Graph Theory, Transversals
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFMA-4158-2022
- ISSN
- 1654-6229
- other publication id
- 2022:K27
- language
- English
- id
- 9088771
- date added to LUP
- 2024-05-13 16:22:19
- date last changed
- 2024-05-13 16:22:19
@misc{9088771, abstract = {{The main focus of this thesis is to study Hall’s Marriage Theorem, which was named after, and proven by the English mathematician Philip Hall in 1935 [6]. The theorem can be stated in terms of different mathematical fields and there are several equivalent theorems proven by other mathematicians [3]. This thesis is mainly going to focus on the graph-theoretic formulation. When stated in terms of graph theory, Hall’s Marriage Theorem gives necessary and suffi- cient conditions for the existence of a special type of edge sets called perfect matchings. The second half of the thesis is dedicated to the applications of the theorem, as well as some of its connections to group theory.}}, author = {{Eklund, Rasmus}}, issn = {{1654-6229}}, language = {{eng}}, note = {{Student Paper}}, series = {{Bachelor's Theses in Mathematical Sciences}}, title = {{Hall’s Marriage Theorem and Related Aspects}}, year = {{2022}}, }