This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Meunier, F. Search for Related Content

Discrete Splittings of the Necklace

LVMT, Ecole Nationale des Ponts et Chaussées, 77455 Marne-la-Vallée CEDEX 2, France
frederic.meunier{at}enpc.fr

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.

Key Words: constructive proof; cubical complex; splitting necklaces
History: Received: July 28, 2006; revision received: December 1, 2007;