Discrete splittings of the necklace

被引：12

作者：

Meunier, Frederic ^{[1
]}

机构：

[1] Ecole Natl Ponts & Chaussees, LVMT, F-77455 Marne La Vallee 2, France

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2008年 / 33卷 / 03期

关键词：

constructive proof; cubical complex; splitting necklaces;

D O I：

10.1287/moor.1080.0311

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：678 / 688

页数：11

共 15 条

[1] SPLITTING NECKLACES
ALON, N
[J]. ADVANCES IN MATHEMATICS, 1987, 63 (03) : 247 - 253
[2] THE BORSUK-ULAM THEOREM AND BISECTION OF NECKLACES
ALON, N
WEST, DB
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1986, 98 (04) : 623 - 628
[3] Alon N, 1991, P INT C MATH KYOT 19, P1421
[4] Algorithmic Construction of Sets for k-Restrictions
Alon, Noga
Moshkovitz, Dana
Safra, Shmuel
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2006, 2 (02) : 153 - 177
[5] Complexity results on restricted instances of a paint shop problem for words
Bonsma, P
Epping, T
Hochstättler, W
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (09) : 1335 - 1343
[6] GENERALIZATIONS OF BAXTER THEOREM AND CUBICAL HOMOLOGY
EHRENBORG, R
HETYEI, G
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1995, 69 (02) : 233 - 287
[7] Complexity results on a paint shop problem
Epping, T
Hochstättler, W
Oertel, P
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 136 (2-3) : 217 - 226
[8] Fan K., 1960, ARCH MATH, V11, P368
[9] BISECTION OF CIRCLE COLORINGS
GOLDBERG, CH
WEST, DB
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (01): : 93 - 106
[10] MATOUSEK J, 2003, USING BORSUKULAM THE

← 1 2 →