Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Improved bounds on the length of maximal abelian square-free words. | Improved bounds on the length of maximal abelian square-free words Evan M. Bullock Department of Mathematics Rice University Houston Texas USA evanmb@ Submitted Sep 28 2003 Accepted Feb 9 2004 Published Feb 20 2004 MR Subject Classifications 68R15 05D99 Abstract A word is abelian square-free if it does not contain two adjacent subwords which are permutations of each other. Over an alphabet Ek on k letters an abelian square-free word is maximal if it cannot be extended to the left or right by letters from Ek and remain abelian square-free. Michael Korn proved that the length k of a shortest maximal abelian square-free word satisfies 4k 7 k 6k 10 for k 6. In this paper we refine Korn s methods to show that 6k 29 k 6k 12 for k 8. 1 Introduction We consider words over an alphabet of k letters which will be taken to be Ek 0 1 . k 1 . We say b is a subword of d if d is the concatenation abc where a and c are words possibly empty. An abelian square is a word of the form a1a2 anaT 1 aT 2 aT n where the ai are letters and T is a permutation of 1 . n . A word is abelian square-free if it does not contain a nonempty subword which is an abelian square. For example any word in which the same letter appears twice in a row is not abelian square-free. A word w over Ek is left-maximal if for every a E Ek the word aw contains an abelian square subword beginning with the initial a. In particular an abelian square-free word w is left-maximal over Ek if aw contains an abelian square for every a E Ek. Similarly a word w is right-maximal over Ek if for every a E Ek wa contains an abelian square 26 Greenough St. Newton MA 02465 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R17 1 subword ending with the final a. A word is maximal over E if it is both left-maximal and right-maximal. Abelian square-free words were first introduced by Erdos 4 who asked for a characterization of alphabet sizes for which arbitrary long abelian square-free words exist see 5 8 and 6 . Maximal abelian .
