pipette
ENEnglish

Tight degeneracy bounds in online Ramsey games

Wen Chen, Qizhong Lin, Shixi Song

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 6 pages