TAILIEUCHUNG - Báo cáo toán học: "Improved bounds on the length of maximal abelian square-free word"

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 .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.