Graph Ramsey games

zbMATH Open1001.91011arXivcs/9911004MaRDI QIDQ4536688FDOQ4536688

Wolfgang Slany

Publication date: 12 December 2002

Abstract: We consider combinatorial avoidance and achievement games based on graph Ramsey theory: The players take turns in coloring still uncolored edges of a graph G, each player being assigned a distinct color, choosing one edge per move. In avoidance games, completing a monochromatic subgraph isomorphic to another graph A leads to immediate defeat or is forbidden and the first player that cannot move loses. In the avoidance+ variants, both players are free to choose more than one edge per move. In achievement games, the first player that completes a monochromatic subgraph isomorphic to A wins. Erdos & Selfridge (1973) were the first to identify some tractable subcases of these games, followed by a large number of further studies. We complete these investigations by settling the complexity of all unrestricted cases: We prove that general graph Ramsey avoidance, avoidance+, and achievement games and several variants thereof are PSPACE-complete. We ultra-strongly solve some nontrivial instances of graph Ramsey avoidance games that are based on symmetric binary Ramsey numbers and provide strong evidence that all other cases based on symmetric binary Ramsey numbers are effectively intractable. Keywords: combinatorial games, graph Ramsey theory, Ramsey game, PSPACE-completeness, complexity, edge coloring, winning strategy, achievement game, avoidance game, the game of Sim, Polya's enumeration formula, probabilistic counting, machine learning, heuristics, Java applet

Full work available at URL: https://arxiv.org/abs/cs/9911004

zbMATH Keywords

complexitycombinatorial gamesgraph Ramsey theoryPSPACE-completenessedge coloringwinning strategyavoidance gameJava appletachievement gameRamsey gameendgamesgame of Sim

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Combinatorial games (91A46)

Cited In (7)

• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
• Upper bounds on positional Paris-Harrington games
• On strong avoiding games
• Title not available (Why is that?)
• Size Ramsey number of bounded degree graphs for games
• Complexity of maker-breaker games on edge sets of graphs
• Transitive avoidance games

   Recommendations

• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Two graph-colouring games 👍 👎
• On the computational complexity and strategies of online Ramsey theory 👍 👎

This page was built for publication: Graph Ramsey games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4536688)