2010/10/27 by Wesley Pegden, Pegden, Wesley
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1010.5772
arxiv created 2010/10/27 · openalex publication_date 2010/10/27 · arxiv updated 2010/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.