Avoiding Generalized Repetitive Patterns in Words

点击翻译按钮获取中文摘要

My proposed research program is in the area of combinatorics on words.  This is an area of pure mathematics.  My proposed research is on the topic of the avoidability of repetitions in words. This area of  study originated with the work of Axel Thue (1906), who showed how to construct an infinite word using just three symbols such that this word never contains the same sequence of symbols repeated twice in a row. An occurrence of such a repetitive pattern (like the word "tartar") is called a "square" and is represented symbolically as the pattern XX. Thue's work has been generalized in many ways by  considering various other types of repetitive patterns: patterns with reversal, circular words, abelian repetitions, fractional repetitions etc. Patterns with reversal consist of repetitive structures such as XXR, which denotes a word followed by its reversal (i.e., an even length palindrome like "redder"). Interest in these types of patterns was sparked by two papers I wrote with Currie: one on the pattern (with reversal) XXRX and the other on the pattern (with reversal) XXXR. In each case we estimated the number of words over a binary alphabet that avoided the pattern in question. We found that in both cases the number of words avoiding the pattern had a very unusual growth. In previous work with Currie and Mol, we partially characterized the avoidable patterns with reversal. I would like to continue this work and complete the characterization. Another problem that I will study concerns "circular words". A circular word is a word whose symbols are arranged on a circle (rather than linearly on a straight line). Recently, with Currie and Mol, we completed the last cases of a conjecture of Gorbunova (2012) concerning which repetitions could be avoided by circular words over a given alphabet. Gorbunova's conjecture involved a "strong" definition of avoidability.  There are weaker definitions for which the analogous questions remain open. I would like to study these versions of avoidability. Another variant of Thue's problem concerns the avoidance of Abelian repetitions. For example, the Abelian variant of the square pattern XX instead consists of a word whose first half is not necessarily identical to its second half, but rather is an anagram of its second half. For example "reappear" is an Abelian instance of XX, since "pear" is an anagram of "reap". With Shallit and Currie, we plan to  improve the current estimates on the number of words of length n that avoid abelian squares, cubes, etc. This research is theoretical in nature; the most common applications of combinatorics on words are to other areas of mathematics, such as algebra and number theory.  However, some results in this area have been successfully applied to problems in bioinformatics (like sequence assembly,where short DNA strings are assembled into whole genome sequences), random number generation, and coding theory.