Back to Search Start Over

A geometric Hall-type theorem

Authors :
Holmsen, Andreas
Martinez-Sandoval, Leonardo
Montejano, Luis
Source :
Proceedings of the American Mathematical Society, 144: 503-511, 2016
Publication Year :
2014

Abstract

We introduce a geometric generalization of Hall's marriage theorem. For any family $F = \{X_1, \dots, X_m\}$ of finite sets in $\mathbb{R}^d$, we give conditions under which it is possible to choose a point $x_i\in X_i$ for every $1\leq i \leq m$ in such a way that the points $\{x_1,...,x_m\}\subset \mathbb{R}^d$ are in general position. We give two proofs, one elementary proof requiring slightly stronger conditions, and one proof using topological techniques in the spirit of Aharoni and Haxell's celebrated generalization of Hall's theorem.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
Proceedings of the American Mathematical Society, 144: 503-511, 2016
Publication Type :
Report
Accession number :
edsarx.1412.6639
Document Type :
Working Paper
Full Text :
https://doi.org/10.1090/proc12733