PreprintarXiv licencearXiv
Tight degeneracy bounds in online Ramsey games
Abstract
In the q-color online Ramsey game, Builder and Painter play on an infinite independent set of vertices. At each step, Builder draws an edge and Painter immediately assigns it one of q colors. Builder aims to force a monochromatic copy of a fixed graph H. We prove that, for every q ≥ 2 and d ≥ 1, Builder can force a monochromatic copy of any d-degenerate graph H while drawing a graph of degeneracy at most d. The bound d is tight, and this resolves in the affirmative a problem of Conlon, Fox and Sudakov.
Related
- Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
- Ordered Ramsey numbers of 3-uniform hypergraphs with bounded weak degeneracy
- Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
- Ramsey-type results for Maker-Breaker games
- Upper and lower bounds for heat kernels with very strong degeneracy
BibTeX
@misc{chen2026tight,
title = {{Tight degeneracy bounds in online Ramsey games}},
author = {Wen Chen and Qizhong Lin and Shixi Song},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01516},
eprint = {2610.01516},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01516},
}
RIS
TY - UNPB
TI - Tight degeneracy bounds in online Ramsey games
AU - Wen Chen
AU - Qizhong Lin
AU - Shixi Song
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01516
UR - https://arxiv.org/abs/2610.01516
AB - In the q-color online Ramsey game, Builder and Painter play on an infinite independent set of vertices. At each step, Builder draws an edge and Painter immediately assigns it one of q colors. Builder aims to force a monochromatic copy of a fixed graph H. We prove that, for every q ≥ 2 and d ≥ 1, Builder can force a monochromatic copy of any d-degenerate graph H while drawing a graph of degeneracy at most d. The bound d is tight, and this resolves in the affirmative a problem of Conlon, Fox and Sudakov.
ER -