Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Thue-like sequences and rainbow arithmetic progressions Jaroslaw Grytczuk | Thue-like sequences and rainbow arithmetic progressions Jaroslaw Grytczuk Institute of Mathematics University of Zielona Gora 65-246 Zielona Gora Poland Submitted October 21 2002 Accepted November 6 2002. MR Subject Classifications 05C38 15A15 15A18 Abstract A sequence u is said to be nonrepetitive if no two adjacent blocks of u are exactly the same. For instance the sequence abcbcba contains a repetition bcbc while abcacbabcbac is nonrepetitive. A well known theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set a b c . This fact implies via Konig s Infinity Lemma the existence of an infinite ternary sequence without repetitions of any length. In this paper we consider a stronger property defined as follows. Let k 2 be a fixed integer and let C denote a set of colors or symbols . A coloring f N C of positive integers is said to be k-nonrepetitive if for every r 1 each segment of kr consecutive numbers contains a k-term rainbow arithmetic progression of difference r. In particular among any k consecutive blocks of the sequence f f 1 f 2 f 3 . no two are identical. By an application of the Lovasz Local Lemma we show that the minimum number of colors in a k-nonrepetitive coloring is at most 2-1 ek 2k 1 k 1 k2 k 1 1. Clearly at least k 1 colors are needed but whether O k suffices remains open. This and other types of nonrepetitiveness can be studied on other structures like graphs lattices Euclidean spaces etc. as well. Unlike for the classical Thue sequences in most of these situations non-constructive arguments seem to be unavoidable. A few of a range of open problems appearing in this area are presented at the end of the paper. Keywords nonrepetitive sequence rainbow arithmetic progression chessboard coloring 1 Introduction In this paper we consider another variant of the nonrepetitive sequences of Thue. A hnite sequence u of symbols from a set C is called nonrepetitive if it does THE .
