Asymptotic online size Ramsey conjecture for even cycles versus paths

Let C2kC_{2k} be the cycle of length 2k2k, let PnP_n be the path on nn vertices, and let r~(G,H)\tilde{r}(G,H) denote the online size Ramsey number for graphs GG and HH. The parameter kk is fixed.

Even-cycle online Ramsey conjecture.

r~(C2k,Pn)=2n+o(n)for every fixed k3.\tilde{r}(C_{2k},P_n)=2n+o(n)\quad\text{for every fixed }k\ge 3.

The theorem in the paper establishes the exact value r~(C4,Pn)=2n2\tilde{r}(C_4,P_n)=2n-2 for n8n\ge 8, while previously known bounds show that avoiding odd cycles is asymptotically more difficult for Painter. The conjecture asserts that every fixed even cycle of length at least six has the same leading asymptotic online size Ramsey number as C4C_4 against a path.

Sources & referencesView supporting material

Primary source

Grzegorz Adamski and Małgorzata Bednarska-Bzdęga, “Online size Ramsey numbers: Path vs C_4”, arXiv:2211.12204 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.