The Wonders of Walter's Word
by
Kirby A. Baker
UCLA

One of Walter Taylor's interests has been Combinatorics on Words. A basic problem in this subject is to find patterns that are unavoidable in sufficiently long words (strings of symbols) from small alphabets but not from larger alphabets. The patterns themselves are also represented by words. For example, the pattern word xx represents a pattern consisting of a block that is immediately repeated. This pattern is unavoidable on a two-symbol alphabet but is avoidable by arbitrarily long words on three symbols. The pattern word abxbayaczcawbc, known to insiders as "Walter's Word", is unavoidable by sufficiently long words on a three-symbol alphabet but not on a four-symbol alphabet. The talk will review this and other surprising properties of Walter's Word and will discuss current progress on the interesting questions it raises.

Date received: July 1, 2004

Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caoc-09.