TOPICS
Search

Hadwiger-Debrunner Number


The Hadwiger-Debrunner number HD_d(p,q) is the least integer N such that every finite family of at least p nonempty compact convex sets in R^d with the (p,q)-property can be met by at most N points. The (p,q)-property means that among every p members of the family, some q have a common point. For p>=q>=d+1, this number is finite by the (p,q)-theorem of Alon and Kleitman (1992), which generalizes Helly's theorem.

For fixed integers q>d>=2, Chen et al. (2026) proved

 HD_d(p,q)>=p^((d+q-2)/(q-1)-o(1))

as p->infty, where o denotes little-O notation. In particular, the planar bound for q=3 is HD_2(p,3)>=p^(3/2-o(1)). Their complementary constructions also give HD_d(p,d+1)>=p^(|_(d+1)/2_|-o(1)) for fixed d>=3, where |_x_| is the floor function.

Other parameter ranges benefit from different constructions. For fixed integers a>=3, they obtain HD_(2a+1)(p,4a+1)>=p^(2-1/a-o(1)). For fixed a>=4, they obtain HD_(3a+2)(p,5a)>=p^(5/2-o(1)). Chen et al. (2026) credit GPT-6 Astra with assisting the proof of their linear-reduction theorem and the quantitative optimization.


See also

Convex Set, Helly's Theorem

Explore with Wolfram|Alpha

References

Alon, N. and Kleitman, D. J. "Piercing Convex Sets and the Hadwiger-Debrunner (p,q)-Problem." Adv. Math. 96, 103-112, 1992. https://doi.org/10.1016/0001-8708(92)90052-M.Chen, W.; Ge, G.; and Shu, Y. "Hadwiger-Debrunner Numbers from Rainbow Turán Numbers and Beyond." 14 Nov 2026. https://arxiv.org/abs/2611.19281v1.

Cite this as:

Weisstein, Eric W. "Hadwiger-Debrunner Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Hadwiger-DebrunnerNumber.html

Subject classifications