×

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

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.)

Citations:

Zbl 0956.05075
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.