pipette
ESEspañol

Tight degeneracy bounds in online Ramsey games

Wen Chen, Qizhong Lin, Shixi Song

Preprint

In the authors' words

In the -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 colors. Builder aims to force a monochromatic copy of a fixed graph . We prove that, for every and , Builder can force a monochromatic copy of any -degenerate graph while drawing a graph of degeneracy at most . The bound is tight, and this resolves in the affirmative a problem of Conlon, Fox and Sudakov.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 6 pages