Ramsey-type results for Maker-Breaker games
Abstract
A graph G is minimal Ramsey for a graph H if every $2$-colouring of the edges of G contains a monochromatic copy of H, but for every proper subgraph of G, there is a $2$-colouring that does not contain such a monochromatic copy. Characterizing minimal Ramsey graphs is a widely studied problem. Recent research in this field includes the characterization of the size of the set ℳ2(H) of all minimal Ramsey graphs for H, or finding the smallest minimum degree among all graphs in ℳ2(H). In this paper, we introduce a game theoretic analogue of the above concept by considering the Maker-Breaker H-game on a graph G. In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G, and Maker wins if in the end of the game the graph spanned by Maker's edges contains a copy of H. Otherwise, Breaker wins the game. We call a graph G winnable for H if Maker has a winning strategy for the Maker-Breaker H-game on G, and we call it minimal winnable if additionally Breaker wins the H-game on every proper subgraph of G. Along the lines of minimal-Ramsey theory, we characterize all graphs H for which there exist infinitely many minimal winnable graphs, and we prove tight bounds for the smallest minimum degree among all these minimal winnable graphs. Amongst others, we obtain precise results for trees, cycles, cliques, and complete bipartite graphs. In general, we find many similarities between the Ramsey setting and the Maker-Breaker setting, but we also show substantial differences.
Related
- Maker Breaker Games on a Budget
- Tight degeneracy bounds in online Ramsey games
- New results on the odd- and unique-Ramsey numbers
- New strategies for some pursuit-evasion differential games with Gronwall-type constraints
- Analysis of First-Order Linear Pursuit and Evasion Differential Games with Gronwall-Type Constraints
BibTeX
@misc{allin2026ramseytype,
title = {{Ramsey-type results for Maker-Breaker games}},
author = {Alexander Allin and Juri Barkey and Dennis Clemens},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02588},
eprint = {2609.02588},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02588},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Ramsey-type results for Maker-Breaker games
AU - Alexander Allin
AU - Juri Barkey
AU - Dennis Clemens
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02588
UR - https://arxiv.org/abs/2609.02588
AB - A graph G is minimal Ramsey for a graph H if every $2$-colouring of the edges of G contains a monochromatic copy of H, but for every proper subgraph of G, there is a $2$-colouring that does not contain such a monochromatic copy. Characterizing minimal Ramsey graphs is a widely studied problem. Recent research in this field includes the characterization of the size of the set ℳ_2(H) of all minimal Ramsey graphs for H, or finding the smallest minimum degree among all graphs in ℳ_2(H). In this paper, we introduce a game theoretic analogue of the above concept by considering the Maker-Breaker H-game on a graph G. In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G, and Maker wins if in the end of the game the graph spanned by Maker's edges contains a copy of H. Otherwise, Breaker wins the game. We call a graph G winnable for H if Maker has a winning strategy for the Maker-Breaker H-game on G, and we call it minimal winnable if additionally Breaker wins the H-game on every proper subgraph of G. Along the lines of minimal-Ramsey theory, we characterize all graphs H for which there exist infinitely many minimal winnable graphs, and we prove tight bounds for the smallest minimum degree among all these minimal winnable graphs. Amongst others, we obtain precise results for trees, cycles, cliques, and complete bipartite graphs. In general, we find many similarities between the Ramsey setting and the Maker-Breaker setting, but we also show substantial differences.
ER -