2021/11/28 by Grzegorz Adamski, Adamski, Grzegorz, Małgorzata Bednarska-Bzdȩga +1 · 1 citation
Computer Science · Mathematics · #05C55 #05C57 #91A46 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2111.14147
openalex publication_date 2021/11/28 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Given two graph families \mathcal H1 and \mathcal H2, a size Ramsey game is played on the edge set of K_ℕ. In every round, Builder selects an edge and Painter colours it red or blue. Builder is trying to force Painter to create as soon as possible a red copy of a graph from \mathcal H1 or a blue copy of a graph from \mathcal H2. The online (size) Ramsey number r(\mathcal H1,\mathcal H2) is the smallest number of rounds in the game provided Builder and Painter play optimally. We prove that if \mathcal H1 is the family of all odd cycles and \mathcal H2 is the family of all connected graphs on n vertices and m edges, then r(\mathcal H1,\mathcal H2)≥ φn + m-2φ+1, where φ is the golden ratio, and for n≥ 3, m≤ (n-1)2/4 we have r(\mathcal H1,\mathcal H2)≤ n+2m+O(√(m-n+1)). We also show that r(C3,Pn)≤ 3n-4 for n≥ 3. As a consequence we get 2.6n-3≤ r(C3,Pn)≤ 3n-4 for every n≥ 3.