Complexity and Periodicity<br> <em>Introduced by: Tom Trotter</em>

Thursday, November 29, 2012 - 3:30pm - 4:30pm
Keller 3-180
Bryna Kra (Northwestern University)
The interaction between combinatorics and dynamics is a classical subject and an illustration of this interaction arises in the combinatorics of words. The Morse-Hedlund Theorem states that an infinite word in a finite alphabet is periodic if and only if there is exists a positive integer n such that the complexity (the number of words of length n) is bounded by n. A natural approach to this theorem is via analyzing the dynamics of the Z-action associated to the word. Periodicity and complexity have natural generalizations to higher dimensions, but there is no simple analog of the Morse-Hedlund Theorem. I will give an overview of results in higher dimensions, including progress on a conjecture of Nivat in 2 dimensions. This is joint work with Van Cyr.
MSC Code: