betaFeedback

WorksMathematics

Hadwiger-Debrunner numbers from rainbow Turán numbers and beyond

Abstract

The Hadwiger-Debrunner number HD⁡d(p,q)\operatorname{HD}_d(p,q) is defined as the maximum piercing number over all finite families of compact convex sets in Rd\mathbb R^d in which among every pp sets, some qq have non-empty intersection. We develop three complementary constructions that improve lower bounds for Hadwiger-Debrunner numbers. For any fixed q>d≥2q>d\ge 2, a randomly sparsified family of hyperplanes, analyzed using hypergraph containers, yields HD⁡d(p,q)≥p(d+q−2)/(q−1)+o(1)\operatorname{HD}_d(p,q)\ge p^{(d+q-2)/(q-1)+o(1)} as p→∞p\rightarrow\infty. To deduce further bounds, we establish a transfer argument from upper bounds on the sizes of sufficiently general-positioned subsets of high-dimensional integer grids to lower bounds for Hadwiger-Debrunner numbers. Two methodologies are adopted to derive the former: one connects rainbow Turán theory and general-positioned grid sets, and the other uses full spark linear reduction of tuples with bounded-size preimages. As a combinatorial ingredient, we describe the rainbow Turán behavior under suspension operations, which may be of independent interest.

Paper details

vlnc:W_8bp35svb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6 astra

View statement
Looking for related papers…