## Lecture Summaries -- Winter 2017

These summaries will be added as the course takes place.

### Week 1

Lecture 1: Wednesday, January 4, 2017:

Information about the course. Marking, exams, Piazza, etc.
Course textbook. Course outline. Introduction to combinatorics on
words (Chapter 2 of textbook). Basic operations on words: concatenation,
reverse, power, perfect shuffle. Basic operations on languages: union,
intersection, complement, concatenation. Proofs by induction.
The Lyndon-Schutzenberger theorems.

### Week 2

Lecture 2: Monday, January 9 2017:

The textbook is still not in the bookstore, but they are promising it
soon. In the meantime, there is a copy of the textbook on reserve in the
library. More on the Lyndon-Schutzenberger theorems; see the
handout. Primitive words. The
primitive words problem. I offer
an automatic 100 for the course, and $200, for a solution. Introduction
to the Fine-Wilf theorem (Theorem 2.3.5). Problem
Set 1 is now available.
Lecture 3: Wednesday, January 11 2017:

The textbook is now available. We did Theorem 2.3.5 (the Fine-Wilf
theorem). Conjugates. Bordered and unbordered words. Theorem 2.4.2. Theorem 2.4.3: a word
is primitive if and only if it has an unbordered conjugate. Problem-solving
in small groups, session 1.

### Week 3

Lecture 4: Monday, January 16 2017:

Repetitions in words. Overlaps. Squares. The Thue-Morse sequence **t**.
Definition. The sequence **t** avoids overlaps (we did the
alternative proof here). Constructing
an infinite word that avoids squares. Properties of the Thue-Morse
sequence. (For more about the Thue-Morse sequence, you can
read this
survey paper or this recent column by
James Propp.)
Open problem: say something interesting about the
lexicographically least squarefree word
over the alphabet {0, 1, 2}.
Lecture 5: Wednesday, January 18 2017:

Finite automata and regular languages. Quotient, morphisms, substitutions.
Closure of regular languages under these operations. Problem-solving in
small groups, session2.