Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of 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
Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên