比利时vs摩洛哥足彩
,
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
****************************