Graph Ramsey games

MaRDI QIDQ4536688zbMATH OpenFDO

Authors Wolfgang Slany

Publication date 12 December 2002

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)

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

Recommendations

• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
• scientific article; zbMATH DE number 969183
• scientific article; zbMATH DE number 3900800
• Two graph-colouring games
• On the computational complexity and strategies of online Ramsey theory

Cited in

(10)

• The general position avoidance game and hardness of general position games
• On strong avoiding games
• A note on the one-colour avoidance game on graphs
• Complexity of maker-breaker games on edge sets of graphs
• Avoidance game on Steiner triple systems
• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
• Upper bounds on positional Paris-Harrington games
• Transitive avoidance games
• scientific article; zbMATH DE number 3885959 (Why is no real title available?)
• Size Ramsey number of bounded degree graphs for games

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)