Premium
Highly nonrepetitive sequences: Winning strategies from the local lemma
Author(s) -
Pegden Wesley
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20354
Subject(s) - lemma (botany) , graph , mathematics , extension (predicate logic) , computer science , theoretical computer science , combinatorics , discrete mathematics , programming language , ecology , poaceae , biology
We prove game‐theoretic versions of several classical results on nonrepetitive sequences, showing the existence of winning strategies using an extension of the Lovász Local Lemma which can dramatically reduce the number of edges needed in a dependency graph when there is an ordering underlying the significant dependencies of events. This appears to represent the first successful application of a Local Lemma to games. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011