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

DOI10.1515/ADVGEOM-2017-0028zbMATH Open1431.52011arXiv1508.02380OpenAlexW2761160398MaRDI QIDQ1707415FDOQ1707415

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

Publication date: 29 March 2018

Published in: advg (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (20)

• Discrete quantitative Helly-type theorems with boxes
• Helly-type theorems for the diameter
• 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
• Centerpoints: A Link Between Optimization and Convex Geometry
• Quantitative combinatorial geometry for concave functions
• Piercing numbers in approval voting
• The colorful Helly theorem and colorful resolutions of ideals
• Quantitative Tverberg theorems over lattices and other discrete sets
• Title not available (Why is that?)
• 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
• Centerpoints: a link between optimization and convex geometry
• On maximal \(S\)-free sets and the Helly number for the family of \(S\)-convex sets

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)