Discrete Splittings of the Necklace

Authors :: Frédéric Meunier
Laboratoire Ville, Mobilité, Transport (LVMT )
École des Ponts ParisTech (ENPC)-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Université Paris-Est Marne-la-Vallée (UPEM)
Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)
Source :: Mathematics of Operations Research, Mathematics of Operations Research, INFORMS, 2008, 33 (3), pp.678. ⟨10.1287/moor.1080.0311⟩
Publication Year :: 2008
Publisher :: Institute for Operations Research and the Management Sciences (INFORMS), 2008.
Abstract: International audience; This paper deals with, direct proofs and combinatorial proofs of the famous necklace theorem of Alon, Goldberg, and West. The new results are a direct proof for the case of two thieves and three types of beads, and an efficient constructive proof for the general case with two thieves. This last proof uses a theorem of Ky Fan which is a version of Tucker's lemma concerning cubical complexes instead of Simplicial complexes. © 2008 INFORMS.

Tools