Splitting necklaces and measurable colorings of the real line
HTML articles powered by AMS MathViewer
- by Noga Alon, Jarosław Grytczuk, Michał Lasoń and Mateusz Michałek
- Proc. Amer. Math. Soc. 137 (2009), 1593-1599
- DOI: https://doi.org/10.1090/S0002-9939-08-09699-8
- Published electronically: November 25, 2008
- PDF | Request permission
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 $k$-colored necklace can be fairly split by at most $k$ cuts (from the resulting pieces one can form two collections, each capturing the same measure of every color). Here we prove that for every $k\geq 1$ there is a measurable $(k+3)$-coloring of the real line such that no interval can be fairly split using at most $k$ cuts. In particular, there is a measurable $4$-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
- Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
- Noga Alon, Splitting necklaces, Adv. in Math. 63 (1987), no. 3, 247–253. MR 877785, DOI 10.1016/0001-8708(87)90055-7
- Noga Alon, Jarosław Grytczuk, Mariusz Hałuszczak, and Oliver Riordan, Nonrepetitive colorings of graphs, Random Structures Algorithms 21 (2002), no. 3-4, 336–346. Random structures and algorithms (Poznan, 2001). MR 1945373, DOI 10.1002/rsa.10057
- Noga Alon and Jarosław Grytczuk, Breaking the rhythm on graphs, Discrete Math. 308 (2008), no. 8, 1375–1380. MR 2392054, DOI 10.1016/j.disc.2007.07.063
- Noga Alon and Douglas B. West, The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc. 98 (1986), no. 4, 623–628. MR 861764, DOI 10.1090/S0002-9939-1986-0861764-9
- Dwight R. Bean, Andrzej Ehrenfeucht, and George F. McNulty, Avoidable patterns in strings of symbols, Pacific J. Math. 85 (1979), no. 2, 261–294. MR 574919, DOI 10.2140/pjm.1979.85.261
- T. C. Brown, Research Problems: Is There a Sequence on Four Symbols in Which No Two Adjacent Segments are Permutations of One Another?, Amer. Math. Monthly 78 (1971), no. 8, 886–888. MR 1536459, DOI 10.2307/2316487
- Christian Choffrut and Juhani Karhumäki, Combinatorics of words, Handbook of formal languages, Vol. 1, Springer, Berlin, 1997, pp. 329–438. MR 1469998
- James Currie, Unsolved Problems: Open Problems in Pattern Avoidance, Amer. Math. Monthly 100 (1993), no. 8, 790–793. MR 1542406, DOI 10.2307/2324790
- F. M. Dekking, Strongly nonrepetitive sequences and progression-free sets, J. Combin. Theory Ser. A 27 (1979), no. 2, 181–185. MR 542527, DOI 10.1016/0097-3165(79)90044-X
- Paul Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221–254. MR 177846
- A. A. Evdokimov, Strongly asymmetric sequences generated by a finite number of symbols. , Dokl. Akad. Nauk SSSR 179 (1968), 1268–1271 (Russian). MR 0234842
- Charles H. Goldberg and Douglas B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), no. 1, 93–106. MR 772181, DOI 10.1137/0606010
- Jarosław Grytczuk, Pattern avoiding colorings of Euclidean spaces, Ars Combin. 64 (2002), 109–116. MR 1914201
- Jarosław Grytczuk and Wiesław Śliwa, Non-repetitive colorings of infinite sets, Discrete Math. 265 (2003), no. 1-3, 365–373. MR 1969386, DOI 10.1016/S0012-365X(02)00879-8
- Jarosław Grytczuk, Nonrepetitive colorings of graphs—a survey, Int. J. Math. Math. Sci. , posted on (2007), Art. ID 74639, 10. MR 2272338, DOI 10.1155/2007/74639
- J. Grytczuk, Thue type problems for graphs, points, and numbers, Discrete Math. (2008).
- Veikko Keränen, Abelian squares are avoidable on $4$ letters, Automata, languages and programming (Vienna, 1992) Lecture Notes in Comput. Sci., vol. 623, Springer, Berlin, 1992, pp. 41–52. MR 1250629, DOI 10.1007/3-540-55719-9_{6}2
- M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR 675953
- Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
- John C. Oxtoby, Measure and category, 2nd ed., Graduate Texts in Mathematics, vol. 2, Springer-Verlag, New York-Berlin, 1980. A survey of the analogies between topological and measure spaces. MR 584443, DOI 10.1007/978-1-4684-9339-9
- P. A. B. Pleasants, Non-repetitive sequences, Proc. Cambridge Philos. Soc. 68 (1970), 267–274. MR 265173, DOI 10.1017/s0305004100046077
- A. Thue, Über unendliche Zeichenreichen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Christiania 7 (1906), 1-22.
- A. Thue, Über die gegenseitigen Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Christiania 1 (1912), 1-67.
Bibliographic 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
- MR Author ID: 25060
- 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ł Lasoń
- 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
- Received by editor(s): March 25, 2008
- Received by editor(s) in revised form: July 4, 2008
- Published electronically: November 25, 2008
- Communicated by: Jim Haglund
- © Copyright 2008 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 137 (2009), 1593-1599
- MSC (2000): Primary 05C38, 15A15; Secondary 05A15, 15A18
- DOI: https://doi.org/10.1090/S0002-9939-08-09699-8
- MathSciNet review: 2470817