Splitting Necklaces, with Constraints

Abstract

We prove several versions of Alon's "necklace-splitting theorem", subject to additional constraints, as illustrated by the following results. (1) The "almost equicardinal necklace-splitting theorem" claims that, without increasing the number of cuts, one guarantees the existence of a fair splitting such that each thief is allocated (approximately) one and the same number of pieces of the necklace, provided the number of thieves $r=p^\nu$ is a prime power. (2) The "binary splitting theorem" claims that if $r=2^d$ and the thieves are associated with the vertices of a d-cube then, without increasing the number of cuts, one can guarantee the existence of a fair splitting such that adjacent pieces are allocated to thieves that share an edge of the cube. This result provides a positive answer to the "binary splitting necklace conjecture" of Asada at al. (Conjecture 2.11 in [5]) in the case $r=2^d$.