Improved bounds on the Hadwiger-Debrunner numbers

DOI10.1007/S11856-018-1685-1MaRDI QIDQ1650467zbMATH OpenOpenAlexWikidataFDO

Authors Chaya Keller, Shakhar Smorodinsky, Gábor Tardos

Publication date 3 July 2018

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hadwiger-Debrunner conjectureminimal size of a transversal

Mathematics Subject Classification ID

Transversal (matching) theory (05D15) Helly-type theorems and geometric transversal theory (52A35)

Abstract: Let $H{D}_d(p,q)$ denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in $mathbb{R}^d$ which satisfy the $(p,q)$-property ($pgeqqgeqd+1$). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that $H{D}_d(p,q)$ exists for all $pgeqqgeqd+1$. Specifically, they prove that $H{D}_d(p,d+1)$ is $ildeO(p^{d^2+d})$. We present several improved bounds: (i) For any $qgeqd+1$, $H{D}_d(p,q)=ildeO(p^{dleft(fracq-1q-dight)})$. (ii) For $qgeqlogp$, $H{D}_d(p,q)=ildeO(p+(p/q{)}^d)$. (iii) For every $epsilon>0$ there exists a $p_0=p_0(epsilon)$ such that for every $pgeq{p}_0$ and for every $qgeq{p}^{fracd-1d+epsilon}$ we have: $p-q+1leqH{D}_d(p,q)leqp-q+2$. The latter is the first near tight estimate of $H{D}_d(p,q)$ for an extended range of values of $(p,q)$ since the 1957 Hadwiger-Debrunner theorem. We also prove a $(p,2)$-theorem for families in $mathbb{R}^2$ with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property.

Recommendations

• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Transversal numbers for hypergraphs arising in geometry
• On piercing numbers of families satisfying the \((p,q)_{r}\) property
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem

Cites work

• A note on smaller fractional Helly numbers
• A Problem of Geometry in R n
• A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture
• A Ramsey-Type Result for Convex Sets
• A simple proof of the upper bound theorem
• A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
• An upper-bound theorem for families of convex sets
• Approximation algorithms for maximum independent set of pseudo-disks
• Bounded VC-dimension implies a fractional Helly theorem
• Colourful and fractional \((p,q)\)-theorems
• Convex sets in the plane with three of every four meeting
• scientific article; zbMATH DE number 4017764 (Why is no real title available?)
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• scientific article; zbMATH DE number 2209723 (Why is no real title available?)
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• Intersection patterns of convex sets
• New constructions of weak -nets
• New existence proofs ε-nets
• On the Richter-Thomassen conjecture about pairwise intersecting closed curves
• On the union of \(\kappa\)-curved objects
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Point Selections and Weak ε-Nets for Convex Hulls
• State of the union (of geometric objects)
• The clique problem in intersection graphs of ellipses and triangles
• Transversal numbers for hypergraphs arising in geometry
• Über eine Variante zum Hellyschen Satz

Cited in

(20)

• On piercing numbers of families satisfying the \((p,q)_{r}\) property
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• A family of convex sets in the plane satisfying the (4, 3)-property can be pierced by nine points
• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem
• An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets
• Improved Bounds on Brun’s Constant
• On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
• New lower bounds for the Hilbert numbers using reversible centers
• On a problem of Danzer
• Topological Drawings Meet Classical Theorems from Convex Geometry
• From a \((p,2)\)-theorem to a tight \((p,q)\)-theorem
• On a problem of Danzer
• Helly-type problems
• scientific article; zbMATH DE number 7662166 (Why is no real title available?)
• Topological drawings meet classical theorems from convex geometry
• Fractional Helly theorem for Cartesian products of convex sets
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• An ( _0, k + 2)-theorem for k-transversals
• The quantitative fractional Helly theorem
• A variant of the Hadwiger-Debrunner (p,q)-problem in the plane

This page was built for publication: Improved bounds on the Hadwiger-Debrunner numbers

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