Back to search

University of Waterloo

Infinite Sequences and Pattern Avoidance

Abstract

dc:description.abstract

The study of combinatorics on words dates back at least to the beginning of the 20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains no squares (identical adjacent blocks) <i>xx</i>. This result was eventually used to solve some longstanding open problems in algebra and has remarkable connections to other areas of mathematics and computer science as well. In this thesis we primarily study several variations of the problems studied by Thue in his work on repetitions in words, including some recent connections to other areas, such as graph theory. In Chapter 1 we give a brief introduction to the subject of combinatorics on words. In Chapter 2 we use uniform morphisms to construct an infinite binary word that contains no cubes <i>xxx</i> and no squares <i>yy</i> with |<i>y</i>| &#8805; 4, thus giving a simpler construction than that of Dekking. We also use uniform morphisms to construct an infinite binary word avoiding all squares except 0², 1², and (01)², thus giving a simpler construction than that of Fraenkel and Simpson. We give some new enumeration results for these avoidance properties and solve an open problem of Prodinger and Urbanek regarding the perfect shuffle of infinite binary words that avoid arbitrarily large squares. In Chapter 3 we examine ternary squarefree words in more detail, and in Chapter 4 we study words <i>w</i> satisfying the property that for any sufficiently long subword <i>w'</i> of <i>w</i>, <i>w</i> does not contain the reversal of <i>w'</i> as a subword. In Chapter 5 we discuss an application of the property of squarefreeness to colourings of graphs. In Chapter 6 we study strictly increasing sequences (<i>a</i>(<i>n</i>))<i>n</i>&#8805;0 of non-negative integers satisfying the equation <i>a</i>(<i>a</i>(<i>n</i>)) = <i>dn</i>. Finally, in Chapter 7 we give a brief conclusion and present some open problems.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rampersad, Narad

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • Copyright: 2004, Rampersad, Narad. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1155

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Rampersad, Narad. Infinite Sequences and Pattern Avoidance. University of Waterloo, 2004. http://hdl.handle.net/10012/1155