|
Splitting necklaces and measurable colorings of the real line
Author(s):
Noga
Alon;
Jarosław
Grytczuk;
Michał
Lason;
Mateusz
Michałek
Journal:
Proc. Amer. Math. Soc.
137
(2009),
1593-1599.
MSC (2000):
Primary 05C38, 15A15;
Secondary 05A15, 15A18
Posted:
November 25, 2008
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
A (continuous) necklace is simply an interval of the real line colored measurably with some number of colors. A well-known application of the Borsuk-Ulam theorem asserts that every -colored necklace can be fairly split by at most cuts (from the resulting pieces one can form two collections, each capturing the same measure of every color). Here we prove that for every there is a measurable -coloring of the real line such that no interval can be fairly split using at most cuts. In particular, there is a measurable -coloring of the real line in which no two adjacent intervals have the same measure of every color. An analogous problem for the integers was posed by Erdős in 1961 and solved in the affirmative by Keränen in 1991. Curiously, in the discrete case the desired coloring also uses four colors.
References:
-
- 1.
- J-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003. MR 1997038 (2004k:11028)
- 2.
- N. Alon, Splitting necklaces, Advances in Math. 63 (1987), 247-253. MR 877785 (88f:05010)
- 3.
- N. Alon, J. Grytczuk, M. Hałuszczak, O. Riordan, Nonrepetitive colorings of graphs, Random Struct. Alg. 21 (2002), 336-346. MR 1945373 (2004a:05047)
- 4.
- N. Alon, J. Grytczuk, Breaking the rhythm on graphs, Discrete Math. 308 (2008), 1375-1380. MR 2392054
- 5.
- N. Alon, D. West, The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc. 98 (1986), 623-628. MR 861764 (88b:05017)
- 6.
- D.R. Bean, A. Ehrenfeucht, G.F. McNulty, Avoidable patterns in strings of symbols, Pacific J. Math. 85 (1979), 261-294. MR 574919 (81i:20075)
- 7.
- T.C. Brown, Is there a sequence on four symbols in which no two adjacent segments are permutations of one another? Amer. Math. Monthly 78 (1971), 886-888. MR 1536459
- 8.
- Ch. Choffrut, J. Karhumäki, Combinatorics of words, in: Handbook of Formal Languages, G. Rozenberg, A. Salomaa (Eds.), Springer-Verlag, Berlin-Heidelberg, 1997, 329-438. MR 1469998 (98k:68141)
- 9.
- J.D. Currie, Unsolved problems: Open problems in pattern avoidance, Amer. Math. Monthly 100 (1993), 790-793. MR 1542406
- 10.
- F.M. Dekking, Strongly nonrepetitive sequences and progression-free sets, J. Combin. Theory Ser. A 27 (1979), 181-185. MR 542527 (81b:05027)
- 11.
- P. Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221-254. MR 0177846 (31:2106)
- 12.
- A. A. Evdokimov, Strongly asymmetric sequences generated by a finite number of symbols, Dokl. Akad. Nauk. SSSR 179 (1968), 1268-1271; Soviet Math. Dokl. 9 (1968), 536-539. MR 0234842 (38:3156)
- 13.
- C. H. Goldberg, D. B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), 93-106. MR 772181 (86c:05010)
- 14.
- J. Grytczuk, Pattern avoiding colorings of Euclidean spaces, Ars Combin. 64 (2002), 109-116. MR 1914201 (2003e:05087)
- 15.
- J. Grytczuk, W. Śliwa, Non-repetitive colorings of infinite sets, Discrete Math. 265 (2003), 365-373. MR 1969386 (2004g:68135)
- 16.
- J. Grytczuk, Nonrepetitive colorings of graphs--a survey, Int. J. Math. Math. Sci. (2007), Art. ID 74639, 10 pp. MR 2272338 (2008f:05060)
- 17.
- J. Grytczuk, Thue type problems for graphs, points, and numbers, Discrete Math. (2008).
- 18.
- V. Keränen, Abelian squares are avoidable on 4 letters, Automata, Languages and Programming, Lecture Notes in Computer Science 623, Springer, Berlin, 1992, 41-52. MR 1250629 (94j:68244)
- 19.
- M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. MR 675953 (84g:05002)
- 20.
- J. Matoušek, Using the Borsuk-Ulam theorem, Springer-Verlag, Berlin, 2003. MR 1988723 (2004i:55001)
- 21.
- J. C. Oxtoby, Measure and Category, Grad. Texts in Math. 2, Springer-Verlag, New York-Berlin, 1980. MR 584443 (81j:28003)
- 22.
- P.A.B. Pleasants, Non-repetitive sequences, Proc. Cambridge Philos. Soc. 68 (1970), 267-274. MR 0265173 (42:85)
- 23.
- A. Thue, Über unendliche Zeichenreichen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Christiania 7 (1906), 1-22.
- 24.
- A. Thue, Über die gegenseitigen Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Christiania 1 (1912), 1-67.
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical Society
with MSC
(2000):
05C38, 15A15,
05A15, 15A18
Retrieve articles in all Journals with MSC
(2000):
05C38, 15A15,
05A15, 15A18
Additional Information:
Noga
Alon
Affiliation:
Schools of Mathematics and Computer Science, Raymond and Beverly Sacler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel - and - Institute for Advanced Study, Princeton, New Jersey 08540
Email:
nogaa@tau.ac.il
Jarosław
Grytczuk
Affiliation:
Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, 30-387 Kraków, Poland
Email:
grytczuk@tcs.uj.edu.pl
Michał
Lason
Affiliation:
Faculty of Mathematics and Computer Science, Jagiellonian University, 30-387 Kraków, Poland
Email:
mlason@op.pl
Mateusz
Michałek
Affiliation:
Faculty of Mathematics and Computer Science, Jagiellonian University, 30-387 Kraków, Poland
Email:
wajcha2@poczta.onet.pl
DOI:
10.1090/S0002-9939-08-09699-8
PII:
S 0002-9939(08)09699-8
Keywords:
Measurable coloring,
splitting necklaces
Received by editor(s):
March 25, 2008,
Received by editor(s) in revised form:
July 4, 2008
Posted:
November 25, 2008
Communicated by:
Jim Haglund
Copyright of article:
Copyright
2008,
American Mathematical Society
|