DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Sequence games: using a Local Lemma to show strategies for nonrepetitiveness

Speaker: Wesley Pegden, Rutgers University

Date: Thursday, October 1, 2009 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In 1906, Thue began the study of nonrepetitive sequences by showing the existence of a sequence 21020121012... over three symbols without any consecutive identical blocks. Since then, there has been much research on generalizations and modifications of this kind of nonrepetitiveness. In this talk, we will discuss techniques that can be used to show that many of these modifications and generalizations hold in the setting of a game, where the sequence is produced out of competition between two players (alternately selecting digits), in the sense that a player seeking nonrepetitiveness can achieve it in the face of an adversary trying to foil his plans. Our tool is a one-sided or "lefthanded" generalization of the Lovasz Local Lemma, which can be applied in this game setting in spite of the dependencies introduced by the unknown adversary's strategy.