Transversal numbers over subsets of linear spaces

DOI10.1515/advgeom.2011.028zbMath1250.52006arXiv1002.0948OpenAlexW2963846964MaRDI QIDQ2891065

Gennadiy Averkov, Robert Weismantel

Publication date: 13 June 2012

Published in: Advances in Geometry (Search for Journal in Brave)

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

zbMATH Keywords

mixed integer programminglinear inequalitiesHelly's theoremRadon's theoreminteger latticegeometric transversal theoryfractional Helly numbercertificates of infeasibility

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Mixed integer programming (90C11) Helly-type theorems and geometric transversal theory (52A35)

Related Items (16)

Tight bounds on discrete quantitative Helly numbers ⋮ Duality for mixed-integer convex minimization ⋮ Centerpoints: A Link Between Optimization and Convex Geometry ⋮ The geometry and combinatorics of discrete line segment hypergraphs ⋮ Quantitative Tverberg theorems over lattices and other discrete sets ⋮ Complexity of optimizing over the integers ⋮ Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem ⋮ Unnamed Item ⋮ Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem ⋮ Helly’s theorem: New variations and applications ⋮ Centerpoints: A Link between Optimization and Convex Geometry ⋮ Quantitative \((p, q)\) theorems in combinatorial geometry ⋮ Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization ⋮ Maximal $S$-Free Convex Sets and the Helly Number ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Tverberg theorems over discrete sets of points

Cites Work

• Transversal numbers for hypergraphs arising in geometry
• A fractional Helly theorem for convex lattice sets
• Certificates of linear mixed integer infeasibility
• Convexity in cristallographical lattices
• Integer Programming with a Fixed Number of Variables
• On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice
• An observation on the structure of production sets with indivisibilities

This page was built for publication: Transversal numbers over subsets of linear spaces