Ê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.
Romain Christophe Rémy Fleury, Haoye Qin, Aleksi Antoine Bossart, Zhechen Zhang
, ,