On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers Conference Paper 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 ℝ d which satisfy the (p, q)-property (p≥ q≥ d+ 1). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that HD d (p, q) exists for all p≥ q≥ d+ 1. Specifically, they prove that HD d (p, d+ 1) is Õ (pd 2+ d). This paper has two parts. In the first part we present several improved bounds on HD d (p, q). In particular, we obtain the first near tight estimate of HD d (p, q) for an …

publication date

  • January 1, 2017