Improved bounds on the Hadwiger-Debrunner numbers Academic Article uri icon


  • Abstract: Let $ HD_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 ($ p\geq q\geq d+ 1$). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that $ HD_d (p, q) $ exists for all $ p\geq q\geq d+ 1$. Specifically, they prove that $ HD_d (p, d+ 1) $ is $\tilde {O}(p^{d^ 2+ d}) $.

publication date

  • December 13, 2015