Papers › Online size Ramsey numbers: Path vs C₄
Online size Ramsey numbers: Path vs C₄
Grzegorz Adamski, Małgorzata Bednarska-Bzdęga
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Given two graphs G and H, 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's goal is to force Painter to create a red copy of G or a blue copy of H as soon as possible. The online (size) Ramsey number r̃(G,H) is the number of rounds in the game provided Builder and Painter play optimally. We prove that r̃(C₄,Pₙ)≤2n-2 for every n≥8. The upper bound matches the lower bound obtained by J. Cyman, T. Dzido, J. Lapinskas, and A. Lo, so we get r̃(C₄,Pₙ)=2n-2 for n≥8. Our proof for n≤13 is computer assisted. The bound r̃(C₄,Pₙ)≤2n-2 solves also the "all cycles vs. Pₙ" game for n≥8 - it implies that it takes Builder 2n-2 rounds to force Painter to create a blue path on n vertices or any red cycle.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections