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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Further applications of a power series method for pattern avoidance. | Further applications of a power series method for pattern avoidance Narad Rampersad Department of Mathematics and Statistics University of Winnipeg 515 Portage Avenue Winnipeg Manitoba R3B 2E9 Canada Submitted Jul 31 2009 Accepted Jun 10 2011 Published Jun 21 2011 Mathematics Subject Classification 68R15 Abstract In combinatorics on words a word w over an alphabet E is said to avoid a pattern p over an alphabet A if there is no factor x of w and no non-erasing morphism h from A to E such that h p x. Bell and Goh have recently applied an algebraic technique due to Golod to show that for a certain wide class of patterns p there are exponentially many words of length n over a 4-letter alphabet that avoid p. We consider some further consequences of their work. In particular we show that any pattern with k variables of length at least 4k is avoidable on the binary alphabet. This improves an earlier bound due to Cassaigne and Roth. 1 Introduction In combinatorics on words the notion of an avoidable unavoidable pattern was first introduced independently by Bean Ehrenfeucht and McNulty 1 and Zimin 22 . Let E and A be alphabets the alphabet A is the pattern alphabet and its elements are variables. A pattern p is a non-empty word over A. A word w over E is an instance of p if there exists a non-erasing morphism h A E such that h p w. A pattern p is avoidable if there exists infinitely many words x over a finite alphabet such that no factor of x is an instance of p. Otherwise p is unavoidable. If p is avoided by infinitely many words on an m-letter alphabet then it is said to be m-avoidable. The survey chapter in Lothaire 12 Chapter 3 gives a good overview of the main results concerning avoidable patterns. The author is supported by an NSERC Postdoctoral Fellowship. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P134 1 The classical results of Thue 19 20 established that the pattern xx is 3-avoidable and the pattern xxx is 2-avoidable. Schmidt 17 see
