Obstacles for splitting multidimensional necklaces

Abstract: The well-known "necklace splitting theorem" of Alon asserts that every

k

-colored necklace can be fairly split into

q

parts using at most

t

cuts, provided

k (q - 1) l e q t

. In a joint paper with Alon et al. we studied a kind of opposite question. Namely, for which values of

k

and

t

there is 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

m a t h b b 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 a theorem of Alon. Moreover for

d = 1, q = 2

we get exactly the result of of Alon et al. Additionally, we prove that if a stronger inequality

k (q - 1) > d t + d + q - 1

is satisfied, then there is a measurable

k

-coloring of

m a t h b b 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.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: Obstacles for splitting multidimensional necklaces