Metraipolis › archive › dc_732374fdca15

Ramsey-type results for Maker-Breaker games — arXiv:2609.02588

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.02588
License (as archived)
CC0-1.0
Archived
2026-10-17T05:38:46.617Z
SHA-256 of the archived text
06d6a0d8f4dd61b30b33cc114fb0b8f4eb60028f546fa2246251ecd45da8f614
Stable URL of this page
https://metraipolis.com/documento/dc_732374fdca15

How to cite

Ramsey-type results for Maker-Breaker games — arXiv:2609.02588 — arXiv (en), https://arxiv.org/abs/2609.02588 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_732374fdca15 (Metraipolis archive dc_732374fdca15, sha256 06d6a0d8f4dd61b30b33cc114fb0b8f4eb60028f546fa2246251ecd45da8f614)
BibTeX
@misc{dc732374fdca15,
  title = {Ramsey-type results for Maker-Breaker games — arXiv:2609.02588},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.02588},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_732374fdca15; sha256 06d6a0d8f4dd61b30b33cc114fb0b8f4eb60028f546fa2246251ecd45da8f614},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02588. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathcal{M}_2(H)$ of all minimal Ramsey graphs for $H$, or finding the smallest minimum degree among all graphs in $\mathcal{M}_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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.02588 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:59:51.786Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).