Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Computer Verification of Integer Sequences Avoiding a Pattern
Speaker: Eric Rowland, Hofstra University
Date: Thursday, September 29, 2016 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Is there an infinite sequence on the alphabet {0, 1, 2} containing no block that occurs twice consecutively? Questions like this were investigated a century ago by the Norwegian mathematician Axel Thue, who produced some of the earliest results in combinatorics on words. If a pattern is avoidable on a given alphabet, it is natural to ask about the lexicographically least sequence that avoids the pattern. Occasionally the structure of this sequence can be discovered and proved by hand. But for many patterns this sequence is sufficiently complex that computer-assisted discovery, followed by automated proofs, seems to be necessary to make any progress.