Improved bounds on the Hadwiger–Debrunner numbers

Chaya Keller, Shakhar Smorodinsky, Gábor Tardos

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

16 اقتباسات (Scopus)

ملخص

Let HDd(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 HDd(p, q) exists for all p ≥ q ≥ d + 1. Specifically, they prove that HDd(p, d+1) is Õ(image found). We present several improved bounds: (i) For any q ≥ d+1, HDd(p, q) = Õ (image found). (ii) For q ≥ log p, HDd(p, q) = Õ (p+(p/q)d). (iii) For every ε > 0 there exists a p0 = p0(ε) such that for every p ≥ p0 and for every (image found) we have p − q + 1 ≤ HDd(p, q) ≤ p − q + 2. The latter is the first near tight estimate of HDd(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 ℝ2 with union complexity below a specific quadratic bound.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)925-945
عدد الصفحات21
دوريةIsrael Journal of Mathematics
مستوى الصوت225
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 18 أبريل 2018
منشور خارجيًانعم

بصمة

أدرس بدقة موضوعات البحث “Improved bounds on the Hadwiger–Debrunner numbers'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا