Splitting Necklaces, with Constraints

View/ Open
Date
2020-02-11MFO Scientific Program
Research in Pairs 2019Series
Oberwolfach Preprints;2020,03Author
Jojic, Dusko
Panina, Gaiane
Zivaljevic, Rade
Metadata
Show full item recordOWP-2020-03
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$.