Splitting Necklaces, with Constraints
Date
Volume
Issue
Journal
Series Titel
Book Title
Publisher
Link to publishers version
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ν is a prime power. (2) The "binary splitting theorem" claims that if r=2d 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=2d.
Description
Keywords
Collections
License
This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties.