Applying a Local Lemma to Thue games

-
Wesley Pegden, Rutgers University
Fine Hall 224

In this talk, I will discuss probabilistic proofs for the existence of winning strategies in sequence games where the goal is nonrepetitiveness. The technique involves a 'one-sided' generalization of the Local Lemma, which allows us to ignore the dependencies on `future' events which would normally prevent this kind of proof from working. I will also discuss the extension of these results to graphs. Although many proofs about games are motivated by a probabilistic intuition, these results appear to represent the first successful applications of a Local Lemma to games.