Page 1 of 1

Unavoidable patterns in words (strings)

Posted: Fri Jan 12, 2018 3:24 pm
by Joseph Malkevitch
Dear Colleagues,

There is a surprisingly rich theory in discrete mathematics of the study of strings - patterns of symbols taken from some alphabet, perhaps 0 and 1 or perhaps x, y, and z. Thus one can do algebra on strings by defining, by way of an example, an operation on two strings by juxtaposing them. Thus xy composted with yzx is xyyzx. This string could be written with exponential notation, thus, zz as z^2.

Here is an account of some recent progress made on a problem in the combinatorics of words, which deals with strings and patterns in those strings:

https://gilkalai.wordpress.com/2018/01/ ... -in-words/

This article deals with words of a certain kind (Zimin words) and when they avoid string patterns of certain lengths.

Regards,

Joe