A geometric Hall-type theorem

DOI10.1090/PROC12733MaRDI QIDQ2789848zbMATH OpenOpenAlexFDO

Authors L. Martínez-Sandoval, Andreas Holmsen, L. Montejano

Publication date 2 March 2016

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6639

zbMATH Keywords

Hall's theoremmatroidspoints in general positiontopological combinatorics

Mathematics Subject Classification ID

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

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 $1leqileqm$ in such a way that the points $x_1,\mathrm{...},x_{m}subsetmathbb{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.

Recommendations

• scientific article; zbMATH DE number 4064988
• A generalization of Hall's theorem
• A geometric Gordan-Stiemke theorem
• An extension of Hall's theorem
• A generalization of Hall-Wielandt theorem
• On a theorem of M. Hall
• A GEOMETRIC SPECTRAL THEOREM
• A generalization of a Hall theorem.

Cites work

• A topological colorful Helly theorem
• Domination numbers and homology
• Eigenvalues and homology of flag complexes and vector representations of graphs
• Hall's theorem for hypergraphs
• Homotopy properties of greedoids
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• scientific article; zbMATH DE number 3383912 (Why is no real title available?)
• Independent systems of representatives in weighted graphs
• Nerves, fibers and homotopy groups
• On Forming Committees
• Ryser's conjecture for tripartite 3-graphs
• The clique complex and hypergraph matching
• The intersection of a matroid and a simplicial complex
• Topology of random clique complexes
• Triangulated spheres and colored cliques

Cited in

(7)

• On an application of Hall's representatives theorem to a finite geometry problem
• Triangulated spheres and colored cliques
• Noncover complexes, independence complexes, and domination numbers of hypergraphs
• Domination numbers and noncover complexes of hypergraphs
• Systems of distant representatives in Euclidean space
• Helly’s theorem: New variations and applications
• A generalization of balanced tableaux and marriage problems with unique solutions

This page was built for publication: A geometric Hall-type theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789848)