Journal Article

Obstacles for splitting multidimensional necklaces

Lasoń, Michał

2015

Overview

The well-known “necklace splitting theorem” of Alon (1987) asserts that every kk-colored necklace can be fairly split into qq parts using at most tt cuts, provided k(q−1)≤tk(q-1)\\leq t. In a joint paper with Alon et al. (2009) we studied a kind of opposite question. Namely, for which values of kk and tt is there a measurable kk-coloring of the real line such that no interval has a fair splitting into 22 parts with at most tt cuts? We proved that k>t+2k>t+2 is a sufficient condition (while k>tk>t is necessary). We generalize this result to Euclidean spaces of arbitrary dimension dd, and to arbitrary number of parts qq. We prove that if k(q−1)>t+d+q−1k(q-1)>t+d+q-1, then there is a measurable kk-coloring of Rd\\mathbb {R}^d such that no axis-aligned cube has a fair qq-splitting using at most tt axis-aligned hyperplane cuts. Our bound is of the same order as a necessary condition k(q−1)>tk(q-1)>t implied by Alon’s 1987 work. Moreover, for d=1,q=2d=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−1k(q-1)>dt+d+q-1 is satisfied, then there is a measurable kk-coloring of Rd\\mathbb {R}^d with no axis-aligned cube having a fair qq-splitting using at most tt arbitrary hyperplane cuts. The proofs are based on the topological Baire category theorem and use algebraic independence over suitably chosen fields.

• Publisher: American Mathematical Society
• Subject: Research article