PreprintarXiv licencearXiv
Avoiding two cycles in Avoider--Enforcer games
Abstract
We study the strict and monotone (1:b) Avoider--Enforcer games on the edges of the complete graph Kn. We prove that, for integers n≥2 and b≥6n, Avoider can keep his graph a forest after every move, except possibly the last. Thus, his final graph contains at most one cycle. This answers Question~10 of Clemens, Ehrenmüller, Person, and Tran, which asks whether a bias linear in n is sufficient.
Related
BibTeX
@misc{forcan2026avoiding,
title = {{Avoiding two cycles in Avoider--Enforcer games}},
author = {Jovana Forcan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29522},
eprint = {2610.29522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29522},
}
RIS
TY - UNPB
TI - Avoiding two cycles in Avoider--Enforcer games
AU - Jovana Forcan
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29522
UR - https://arxiv.org/abs/2610.29522
AB - We study the strict and monotone (1:b) Avoider--Enforcer games on the edges of the complete graph K_n. We prove that, for integers n≥2 and b≥6n, Avoider can keep his graph a forest after every move, except possibly the last. Thus, his final graph contains at most one cycle. This answers Question~10 of Clemens, Ehrenmüller, Person, and Tran, which asks whether a bias linear in n is sufficient.
ER -