An (?0, k + 2)-Theorem for k-Transversals

Chaya Keller, Micha A. Perles

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

1 ציטוט ‏(Scopus)

תקציר

A family F of sets satisfies the (p, q)-property if among every p members of F, some q can be pierced by a single point. The celebrated (p, q)-theorem of Alon and Kleitman asserts that for any p ? q ? d + 1, any family F of compact convex sets in Rd that satisfies the (p, q)-property can be pierced by a finite number c(p, q, d) of points. A similar theorem with respect to piercing by (d - 1)-dimensional flats, called (d - 1)-transversals, was obtained by Alon and Kalai. In this paper we prove the following result, which can be viewed as an (?0, k + 2)-theorem with respect to k-transversals: Let F be an infinite family of sets in Rd such that each A ? F contains a ball of radius r and is contained in a ball of radius R, and let 0 ? k < d. If among every ?0 elements of F, some k + 2 can be pierced by a k-dimensional flat, then F can be pierced by a finite number of k-dimensional flats. This is the first (p, q)-theorem in which the assumption is weakened to an (8, ·) assumption. Our proofs combine geometric and topological tools.

שפה מקוריתאנגלית
כותר פרסום המארח38th International Symposium on Computational Geometry, SoCG 2022
עורכיםXavier Goaoc, Michael Kerber
מוציא לאורSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
מסת"ב (אלקטרוני)9783959772273
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יוני 2022
אירוע38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, גרמניה
משך הזמן: 7 יוני 202210 יוני 2022

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך224
ISSN (מודפס)1868-8969

כנס

כנס38th International Symposium on Computational Geometry, SoCG 2022
מדינה/אזורגרמניה
עירBerlin
תקופה7/06/2210/06/22

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'An (?0, k + 2)-Theorem for k-Transversals'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי