Helly numbers of algebraic subsets of R^d and an extension of Doignon's theorem

DOI10.1515/ADVGEOM-2017-0028MaRDI QIDQ1707415zbMATH OpenOpenAlexFDO

Authors Edgardo Roldán-Pensado, Jesús A. De Loera, Reuben N. La Haye, Deborah Oliveros

Publication date 29 March 2018

Published in advg (Search for Journal in Brave)

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

zbMATH Keywords

latticesadditive groupsHelly-type theoremsconvexity spacescolorful theorems

Mathematics Subject Classification ID

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

Abstract: We study $S$-convex sets, which are the geometric objects obtained as the intersection of the usual convex sets in $mathbb{R}^d$ with a proper subset $Ssubsetmathbb{R}^d$. We contribute new results about their $S$-Helly numbers. We extend prior work for $S=mathbb{R}^d$, $mathbb{Z}^d$, and $mathbb{Z}^{d-k}imesmathbb{R}^k$; we give sharp bounds on the $S$-Helly numbers in several new cases. We considered the situation for low-dimensional $S$ and for sets $S$ that have some algebraic structure, in particular when $S$ is an arbitrary subgroup of $mathbb{R}^d$ or when $S$ is the difference between a lattice and some of its sublattices. By abstracting the ingredients of Lov'asz method we obtain colorful versions of many monochromatic Helly-type results, including several colorful versions of our own results.

Recommendations

• Discrete and lexicographic Helly-type theorems
• On maximal \(S\)-free sets and the Helly number for the family of \(S\)-convex sets
• Maximal \(S\)-free convex sets and the Helly number
• Discrete quantitative Helly-type theorems with boxes
• A Helly-type theorem for unions of convex sets

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 3770461 (Why is no real title available?)
• scientific article; zbMATH DE number 45409 (Why is no real title available?)
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1182897 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• A Theorem Concerning the Integer Lattice
• A Tverberg-type generalization of the Helly number of a convexity space
• A fractional Helly theorem for convex lattice sets
• A generalization of Caratheodory's theorem
• A quantitative Doignon-Bell-Scarf theorem
• An observation on the structure of production sets with indivisibilities
• Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
• Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
• Convexity in cristallographical lattices
• Flat transversals to flats and convex sets of a fixed dimension
• Integral points of small height outside of a hypersurface
• Iterated Absolute Values of Differences of Consecutive Primes
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Maximal \(S\)-free convex sets and the Helly number
• On maximal \(S\)-free sets and the Helly number for the family of \(S\)-convex sets
• Partition numbers for trees and ordered sets
• Productivity of the Zariski topology on groups.
• Quantitative Tverberg theorems over lattices and other discrete sets
• Random sampling in computational algebra: Helly numbers and violator spaces
• Restricted successive minima
• The dimension of intersections of convex sets
• Transversal numbers over subsets of linear spaces
• Violator spaces: Structure and algorithms

Cited in

(20)

• Discrete quantitative Helly-type theorems with boxes
• Helly-type theorems for the diameter
• Maximal \(S\)-free convex sets and the Helly number
• Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
• The colorful Helly theorem and colorful resolutions of ideals
• Quantitative combinatorial geometry for concave functions
• Centerpoints: A Link Between Optimization and Convex Geometry
• Piercing numbers in approval voting
• Quantitative Tverberg theorems over lattices and other discrete sets
• scientific article; zbMATH DE number 7662166 (Why is no real title available?)
• Convexity in (Colored) Affine Semigroups
• Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem
• Colorful Helly-type theorems for the volume of intersections of convex bodies
• On Helly numbers of exponential lattices
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Helly’s theorem: New variations and applications
• A mélange of diameter Helly-type theorems
• The geometry and combinatorics of discrete line segment hypergraphs
• On maximal \(S\)-free sets and the Helly number for the family of \(S\)-convex sets
• Centerpoints: a link between optimization and convex geometry

This page was built for publication: Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem

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