Splitting necklaces
type: Item
instance of: scholarly article
title: Splitting necklaces
zbMATH Open document ID: 0635.05008
DOI: 10.1016/0001-8708(87)90055-7
published in: Advances in Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Let N be an opened necklace with \(k\cdot a_ i\) beads of color i, \(1\leq i\leq t\). A k-splitting of this necklace is a partition of the necklace into k parts, each consisting of a finite number of nonoverlapping intervals of beads whose union captures precisely \(a_ i\) beads of color i, \(1\leq i\leq t\). The size of the k-splitting is the number of cuts that form the intervals of the splitting, which is one less than the total number of these intervals. The main result is the following theorem: Every necklace with \(k\cdot a_ i\) beads of color i, \(1\leq i\leq t\), has a k-splitting of size at most (k-1)\(\cdot t\). The number (k-1)\(\cdot t\) is best possible. The author formulates the continuous version of the k-splitting problem and proves that it generalizes the discrete one. The proof of this version is topological.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 55M99
zbMATH DE Number: 4033762
zbMATH Keywords: necklace
zbMATH Keywords: splitting
zbMATH Keywords: partition
author: Noga Alon
MaRDI profile type: Publication
full work available at URL: 0001-8708(87)90055-7
OpenAlex ID: W4206085806
cites work: The Chromatic Number of Kneser Hypergraphs
cites work: The Borsuk-Ulam Theorem and Bisection of Necklaces
cites work: A framework for solving VLSI graph layout problems
cites work: On a Topological Generalization of a Theorem of Tverberg
cites work: Q5520521
cites work: Bisection of Circle Colorings
cites work: A Moment Problem in L 1 Approximation
description: scientific article; zbMATH DE number 4033762