Splitting Necklaces, with Constraints

Loading...
Thumbnail Image
Date
2020
Volume
3
Issue
Journal
Series Titel
Oberwolfach Preprints (OWP)
Book Title
Publisher
Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
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
License
Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
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.