Quantitative (p, q) theorems in combinatorial geometry

DOI10.1016/J.DISC.2017.06.017zbMATH Open1379.52007arXiv1504.01642OpenAlexW2963846517MaRDI QIDQ2012541FDOQ2012541

Pablo Soberón, David Rolnick

Publication date: 1 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We show quantitative versions of classic results in discrete geometry, where the size of a convex set is determined by some non-negative function. We give versions of this kind for the selection theorem of B'ar'any, the existence of weak epsilon-nets for convex sets and the $(p,q)$ theorem of Alon and Kleitman. These methods can be applied to functions such as the volume, surface area or number of points of a discrete set. We also give general quantitative versions of the colorful Helly theorem for continuous functions.

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

Recommendations

• Quantitative combinatorial geometry for continuous parameters
• Quantitative combinatorial geometry for concave functions
• Quantitative fractional Helly and \((p,q)\)-theorems
• Transversal numbers for hypergraphs arising in geometry
• Quantitative Helly-type theorem for the diameter of convex sets

zbMATH Keywords

Tverberg theoremweak epsilon-netHelly theorem\((p,q)\) theoremintersection of convex setsvolume optimization

Mathematics Subject Classification ID

Length, area, volume and convex sets (aspects of convex geometry) (52A38) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Approximation by convex sets (52A27) Helly-type theorems and geometric transversal theory (52A35) Other problems of combinatorial convexity (52A37)

Cites Work

• Title not available (Why is that?)
• A generalization of Caratheodory's theorem
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• Title not available (Why is that?)
• Partition numbers for trees and ordered sets
• Title not available (Why is that?)
• Convexity in cristallographical lattices
• Transversal numbers over subsets of linear spaces
• Convex bodies, economic cap coverings, random polytopes
• The convex floating body.
• A Generalization of Radon's Theorem
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Bounded VC-dimension implies a fractional Helly theorem
• Colourful and fractional \((p,q)\)-theorems
• Helly’s theorem: New variations and applications
• Title not available (Why is that?)
• Über eine Variante zum Hellyschen Satz
• Characterization of f-vectors of families of convex sets in \({\mathbb{R}}^ d\). I: Necessity of Eckhoff's conditions
• Characterization of f-vectors of families of convex sets in \({\mathbb{R}}^ d\). II: Sufficiency of Eckhoff's conditions
• A fractional Helly theorem for convex lattice sets
• Approximation of convex sets by polytopes
• A Tverberg-type result on multicolored simplices
• Point Selections and Weak ε-Nets for Convex Hulls
• An observation on the structure of production sets with indivisibilities
• A Theorem Concerning the Integer Lattice
• Dropping a vertex or a facet from a convex polytope
• Thrifty Approximations of Convex Bodies by Polytopes
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
• Title not available (Why is that?)
• Contraction and expansion of convex sets
• Quantitative Steinitz's theorems with applications to multifingered grasping
• Umbrellas and polytopal approximation of the Euclidean ball
• Constructing a polytope to approximate a convex body
• Helly's Theorem with Volumes
• Quantitative Helly-Type Theorems
• Proof of a conjecture of Bárány, Katchalski and Pach
• Bounding the piercing number
• A variant of the Hadwiger-Debrunner \((p,q)\)-problem in the plane
• Title not available (Why is that?)

Cited In (13)

• Discrete quantitative Helly-type theorems with boxes
• Quantitative Helly-type theorems via hypergraph chains
• Quantitative combinatorial geometry for concave functions
• Quantitative Tverberg theorems over lattices and other discrete sets
• A Mélange of Diameter Helly-Type Theorems
• A note on the colorful fractional Helly theorem
• Tverberg’s theorem is 50 years old: A survey
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Helly’s theorem: New variations and applications
• Bounded VC-dimension implies a fractional Helly theorem
• Quantitative combinatorial geometry for continuous parameters
• Quantitative fractional Helly and \((p,q)\)-theorems
• Positive-fraction intersection results and variations of weak epsilon-nets

This page was built for publication: Quantitative \((p, q)\) theorems in combinatorial geometry

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