OBSTACLES FOR SPLITTING MULTIDIMENSIONAL NECKLACES.

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. In a joint paper with Alon et al. (2009) we studied a kind of opposite question. Namely, for which values of k and t is there a measurable k-coloring of the real line such that no interval has a fair splitting into 2 parts with at most t cuts? We proved that k > 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 Rd 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 ℝ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. [ABSTRACT FROM AUTHOR]