95-10 A Winning Strategy for the Ramsey Graph Game

DIMACS TR: 95-10

A Winning Strategy for the Ramsey Graph Game

Author: Aleksandar Pekec

ABSTRACT
We consider a "Maker-Breaker" version of the Ramsey Graph Game, RG(n), and present a winning strategy for maker requiring less than n(2^n) moves. This is the fastest winning strategy known so far. We also demonstrate how the ideas presented can be used to develop winning strategies for some related combinatorial games.

Keywords: Combinatorial Games, Algorithms on Graphs, Ramsey Theory

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-10.ps.gz

DIMACS Home Page