## A geometric Hall-type theorem

HTML articles powered by AMS MathViewer

- by Andreas F. Holmsen, Leonardo Martinez-Sandoval and Luis Montejano PDF
- Proc. Amer. Math. Soc.
**144**(2016), 503-511 Request permission

## 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,\dots ,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.## References

- Ron Aharoni,
*Ryser’s conjecture for tripartite 3-graphs*, Combinatorica**21**(2001), no. 1, 1–4. MR**1805710**, DOI 10.1007/s004930170001 - Ron Aharoni and Eli Berger,
*The intersection of a matroid and a simplicial complex*, Trans. Amer. Math. Soc.**358**(2006), no. 11, 4895–4917. MR**2231877**, DOI 10.1090/S0002-9947-06-03833-5 - Ron Aharoni, Eli Berger, and Ran Ziv,
*Independent systems of representatives in weighted graphs*, Combinatorica**27**(2007), no. 3, 253–267. MR**2345810**, DOI 10.1007/s00493-007-2086-y - R. Aharoni, E. Berger, and R. Meshulam,
*Eigenvalues and homology of flag complexes and vector representations of graphs*, Geom. Funct. Anal.**15**(2005), no. 3, 555–566. MR**2221142**, DOI 10.1007/s00039-005-0516-9 - Ron Aharoni, Maria Chudnovsky, and Andreĭ Kotlov,
*Triangulated spheres and colored cliques*, Discrete Comput. Geom.**28**(2002), no. 2, 223–229. MR**1920141**, DOI 10.1007/s00454-002-2792-6 - Ron Aharoni and Penny Haxell,
*Hall’s theorem for hypergraphs*, J. Graph Theory**35**(2000), no. 2, 83–88. MR**1781189**, DOI 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V - A. Björner,
*Topological methods*, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR**1373690** - Anders Björner,
*Nerves, fibers and homotopy groups*, J. Combin. Theory Ser. A**102**(2003), no. 1, 88–93. MR**1970978**, DOI 10.1016/S0097-3165(03)00015-3 - Anders Björner, Bernhard Korte, and László Lovász,
*Homotopy properties of greedoids*, Adv. in Appl. Math.**6**(1985), no. 4, 447–494. MR**826593**, DOI 10.1016/0196-8858(85)90021-1 - Jack Edmonds,
*Submodular functions, matroids, and certain polyhedra*, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 69–87. MR**0270945** - P. Hall,
*On representatives of subsets*, J. London Math. Soc.**10**(1935) 26–30. - P. Haxell,
*On forming committees*, Amer. Math. Monthly**118**(2011), no. 9, 777–788. MR**2854000**, DOI 10.4169/amer.math.monthly.118.09.777 - Matthew Kahle,
*Topology of random clique complexes*, Discrete Math.**309**(2009), no. 6, 1658–1671. MR**2510573**, DOI 10.1016/j.disc.2008.02.037 - Gil Kalai and Roy Meshulam,
*A topological colorful Helly theorem*, Adv. Math.**191**(2005), no. 2, 305–311. MR**2103215**, DOI 10.1016/j.aim.2004.03.009 - Roy Meshulam,
*The clique complex and hypergraph matching*, Combinatorica**21**(2001), no. 1, 89–94. MR**1805715**, DOI 10.1007/s004930170006 - Roy Meshulam,
*Domination numbers and homology*, J. Combin. Theory Ser. A**102**(2003), no. 2, 321–330. MR**1979537**, DOI 10.1016/S0097-3165(03)00045-1

## Additional Information

**Andreas F. Holmsen**- Affiliation: Department of Mathematical Sciences, KAIST, Daejeon, South Korea
- MR Author ID: 685253
- Email: andreash@kaist.edu
**Leonardo Martinez-Sandoval**- Affiliation: Instituto de Matemáticas, National University of Mexico at Querétaro, Juriquilla, Querétaro 76230, Mexico – and – Institut de Mathémathiques et de Modélisation de Montpellier, Univesité de Montpellier, Place Eugéne Bataillon, 34095 Montpellier Cedex, France
- MR Author ID: 1004558
- Email: leomtz@im.unam.mx
**Luis Montejano**- Affiliation: Instituto de Matemáticas, National University of Mexico at Querétaro, Juriquilla , Querétaro 76230, Mexico
- MR Author ID: 126505
- Email: luis@matem.unam.mx
- Received by editor(s): December 20, 2014
- Received by editor(s) in revised form: January 8, 2015, and January 14, 2015
- Published electronically: June 26, 2015
- Additional Notes: The first author would like to thank the Instituto de Matemáticas, UNAM at Querétaro for their hospitality and support during his visit. The second and third authors wish to acknowledge support from CONACyT under Project 166306, support from PAPIIT–UNAM under Project IN112614 and support from ECOS Nord project M13M01. The third author was supported by CONACyT Scholarship 277462
- Communicated by: Patricia L. Hersh
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**144**(2016), 503-511 - MSC (2010): Primary 05D15, 52C35
- DOI: https://doi.org/10.1090/proc12733
- MathSciNet review: 3430829