2023/02/17 by Ruyu Song, Sha Wang, Song, Ruyu +3
Computer Science · Mathematics · #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.2302.08787
openalex publication_date 2023/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two graphs G and H, the online Ramsey number r(G,H) is defined to be the minimum number of rounds that Builder can always guarantee a win in the following (G, H)-online Ramsey game between Builder and Painter. Starting from an infinite set of isolated vertices, in each round Builder draws an edge between some two vertices, and Painter immediately colors it red or blue. Builder's goal is to force either a red copy of G or a blue copy of H in as few rounds as possible, while Painter's goal is to delay it for as many rounds as possible. Let K1,3 denote a star with three edges and Pℓ a path with ℓ vertices. Latip and Tan conjectured that r(K1,3, Pℓ)=(3/2+o(1))ℓ [Bull. Malays. Math. Sci. Soc. 44 (2021) 3511--3521]. We show that r(K1,3, Pℓ)=\lfloor 3ℓ/2 \rfloor for ℓ≥ 2, which verifies the conjecture in a stronger form.