Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


A geometric Hall-type theorem

Authors: Andreas F. Holmsen, Leonardo Martinez-Sandoval and Luis Montejano
Journal: Proc. Amer. Math. Soc. 144 (2016), 503-511
MSC (2010): Primary 05D15, 52C35
Published electronically: June 26, 2015
MathSciNet review: 3430829
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Ron Aharoni, Ryser's conjecture for tripartite 3-graphs, Combinatorica 21 (2001), no. 1, 1-4. MR 1805710 (2002c:05157),
  • [2] Ron Aharoni and Eli Berger, The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358 (2006), no. 11, 4895-4917 (electronic). MR 2231877 (2007g:05038),
  • [3] Ron Aharoni, Eli Berger, and Ran Ziv, Independent systems of representatives in weighted graphs, Combinatorica 27 (2007), no. 3, 253-267. MR 2345810 (2008g:05068),
  • [4] 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 (2007b:05148),
  • [5] Ron Aharoni, Maria Chudnovsky, and Andreĭ Kotlov, Triangulated spheres and colored cliques, Discrete Comput. Geom. 28 (2002), no. 2, 223-229. MR 1920141 (2003g:52029),
  • [6] Ron Aharoni and Penny Haxell, Hall's theorem for hypergraphs, J. Graph Theory 35 (2000), no. 2, 83-88. MR 1781189 (2001h:05072),$ \langle $83::AID-JGT2$ \rangle $3.0.CO;2-V
  • [7] A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819-1872. MR 1373690 (96m:52012)
  • [8] Anders Björner, Nerves, fibers and homotopy groups, J. Combin. Theory Ser. A 102 (2003), no. 1, 88-93. MR 1970978 (2004a:55018),
  • [9] 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 (87d:05051),
  • [10] 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 (42 #5828)
  • [11] P. Hall,
    On representatives of subsets,
    J. London Math. Soc. 10 (1935) 26-30.
  • [12] P. Haxell, On forming committees, Amer. Math. Monthly 118 (2011), no. 9, 777-788. MR 2854000 (2012j:05004),
  • [13] Matthew Kahle, Topology of random clique complexes, Discrete Math. 309 (2009), no. 6, 1658-1671. MR 2510573 (2010h:05276),
  • [14] Gil Kalai and Roy Meshulam, A topological colorful Helly theorem, Adv. Math. 191 (2005), no. 2, 305-311. MR 2103215 (2005h:52006),
  • [15] Roy Meshulam, The clique complex and hypergraph matching, Combinatorica 21 (2001), no. 1, 89-94. MR 1805715 (2001m:05089),
  • [16] Roy Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003), no. 2, 321-330. MR 1979537 (2004c:05144),

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05D15, 52C35

Retrieve articles in all journals with MSC (2010): 05D15, 52C35

Additional Information

Andreas F. Holmsen
Affiliation: Department of Mathematical Sciences, KAIST, Daejeon, South Korea

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

Luis Montejano
Affiliation: Instituto de Matemáticas, National University of Mexico at Querétaro, Juriquilla , Querétaro 76230, Mexico

Keywords: Hall's theorem, topological combinatorics, points in general position, matroids.
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society