Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

Hall’s Marriage Theorem and Related Aspects

Eklund, Rasmus LU (2022) In Bachelor's Theses in Mathematical Sciences MATK11 20212
Mathematics (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:
author
Eklund, Rasmus LU
supervisor
organization
course
MATK11 20212
year
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}},
}