Hall's marriage theorem
Teorema de Hall
- Date
- 1935 · confidence high
- Place
- Cambridge, England, United Kingdom
- Credited to
- Philip Hall
- Field
- Knowledge & symbols
What was discovered
Theorem of combinatorics and graph theory giving the necessary and sufficient condition for a finite collection of sets to have a system of distinct representatives, or a finite bipartite graph to have a perfect matching.
What it led to
- Bipartite matching algorithms in computer science
- Development of matroid theory and network flow theory
- Applications in matching economics and resource allocation