A geometric Hall-type theorem. (English) Zbl 1331.05219

Holmsen, Andreas F.; Martinez-Sandoval, Leonardo; Montejano, Luis

Proc. Am. Math. Soc. 144, No. 2, 503-511 (2016).

Summary: 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 R. Aharoni and Haxell’s celebrated generalization of Hall’s theorem [J. Graph Theory 35, No. 2, 83–88 (2000; Zbl 0956.05075)].

MSC:

05D15	Transversal (matching) theory
52C35	Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52B40	Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)

Keywords:

Hall’s theorem; topological combinatorics; points in general position; matroids

Citations:

Zbl 0956.05075

References:

[1]	Aharoni, Ron, Ryser’s conjecture for tripartite 3-graphs, Combinatorica, 21, 1, 1-4 (2001) · Zbl 1107.05307 · doi:10.1007/s004930170001
[2]	Aharoni, Ron; Berger, Eli, The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc., 358, 11, 4895-4917 (electronic) (2006) · Zbl 1108.05023 · doi:10.1090/S0002-9947-06-03833-5
[3]	Aharoni, Ron; Berger, Eli; Ziv, Ran, Independent systems of representatives in weighted graphs, Combinatorica, 27, 3, 253-267 (2007) · Zbl 1164.05020 · doi:10.1007/s00493-007-2086-y
[4]	Aharoni, R.; Berger, E.; Meshulam, R., Eigenvalues and homology of flag complexes and vector representations of graphs, Geom. Funct. Anal., 15, 3, 555-566 (2005) · Zbl 1074.05058 · doi:10.1007/s00039-005-0516-9
[5]	Aharoni, Ron; Chudnovsky, Maria; Kotlov, Andre{\u \i }, Triangulated spheres and colored cliques, Discrete Comput. Geom., 28, 2, 223-229 (2002) · Zbl 1017.52009 · doi:10.1007/s00454-002-2792-6
[6]	Aharoni, Ron; Haxell, Penny, Hall’s theorem for hypergraphs, J. Graph Theory, 35, 2, 83-88 (2000) · Zbl 0956.05075 · doi:10.1002/1097-0118(200010)35:\(2\langle
[7]	Bj{\"o}rner, A., Topological methods. Handbook of combinatorics, Vol.1,2, 1819-1872 (1995), Elsevier, Amsterdam · Zbl 0851.52016
[8]	Bj{\"o}rner, Anders, Nerves, fibers and homotopy groups, J. Combin. Theory Ser. A, 102, 1, 88-93 (2003) · Zbl 1030.55006 · doi:10.1016/S0097-3165(03)00015-3
[9]	Bj{\`“o}rner, Anders; Korte, Bernhard; Lov{\'”a}sz, L{\'a}szl{\'o}, Homotopy properties of greedoids, Adv. in Appl. Math., 6, 4, 447-494 (1985) · Zbl 0642.05014 · doi:10.1016/0196-8858(85)90021-1
[10]	Edmonds, Jack, Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and their Applications, Proc. Calgary Internat. Conf., Calgary, Alta., 1969, 69-87 (1970), Gordon and Breach, New York · Zbl 0243.00004
[11]	[hall] P. Hall, \newblockOn representatives of subsets, \newblockJ. London Math. Soc. 10 (1935) 26-30. · JFM 61.0067.01
[12]	Haxell, P., On forming committees, Amer. Math. Monthly, 118, 9, 777-788 (2011) · Zbl 1233.05158 · doi:10.4169/amer.math.monthly.118.09.777
[13]	Kahle, Matthew, Topology of random clique complexes, Discrete Math., 309, 6, 1658-1671 (2009) · Zbl 1215.05163 · doi:10.1016/j.disc.2008.02.037
[14]	Kalai, Gil; Meshulam, Roy, A topological colorful Helly theorem, Adv. Math., 191, 2, 305-311 (2005) · Zbl 1064.52008 · doi:10.1016/j.aim.2004.03.009
[15]	Meshulam, Roy, The clique complex and hypergraph matching, Combinatorica, 21, 1, 89-94 (2001) · Zbl 1107.05302 · doi:10.1007/s004930170006
[16]	Meshulam, Roy, Domination numbers and homology, J. Combin. Theory Ser. A, 102, 2, 321-330 (2003) · Zbl 1030.05086 · doi:10.1016/S0097-3165(03)00045-1