Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Sergey Kitaev

Reykjavík University

Crucial words for abelian powers

Abstract:

In 1961, Erdös asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form $XX'$ where $X'$ is a permutation of $X$ (called "abelian squares"). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. A natural generalization of the problem is to study "abelian k-th powers", i.e., words of the form $X_1X_2...X_k $where $X_i$ is a permutation of $X_1$ for $2 \le i \le k$. In this talk, I will discuss "crucial words" for abelian k-th powers, i.e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, I will consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004). I will present a solution for abelian cubes (the case k = 3) and state a conjectured solution for the case of $k \ge 4.$ This is joint work with Amy Glen and Bjarni V. Halldórsson (Reykjavík University).

March 3, 2009

3:00 PM

AP&M 7321

****************************