Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
The well-known "necklace splitting theorem" of Alon (1987) asserts that every k-colored necklace can be fairly split into q parts using at most t cuts, provided k(q - 1) t + 2 is a sufficient condition (while k > t is necessary). We generalize this result to Euclidean spaces of arbitrary dimension d, and to arbitrary number of parts q. We prove that if k(q - 1) > t + d + q - 1, then there is a measurable k-coloring of R-d such that no axis-aligned cube has a fair q-splitting using at most t axis-aligned hyperplane cuts. Our bound is of the same order as a necessary condition k(q - 1) > t implied by Alon's 1987 work. Moreover, for d = 1, q = 2 we get exactly the result of the 2009 work. Additionally, we prove that if a stronger inequality k(q - 1) > dt + d + q - 1 is satisfied, then there is a measurable k-coloring of R-d with no axis-aligned cube having a fair q-splitting using at most t arbitrary hyperplane cuts. The proofs are based on the topological Baire category theorem and use algebraic independence over suitably chosen fields.
, , ,
Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên