Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
     

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 $ 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:

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


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google