Lower bounds for online size Ramsey numbers for paths

Given two graphs $H_1$ and $H_2$, an online Ramsey game is played on the edge set of $K_\mathbb{N}$. In every round Builder selects an edge and Painter colors it red or blue. Builder is trying to force Painter to create a red copy of $H_1$ or a blue copy of $H_2$ as soon as possible, while Painter's goal is the opposite. The online (size) Ramsey number $\tilde{r}(H_1,H_2)$ is the smallest number of rounds in the game provided Builder and Painter play optimally. Let $v(G)$ be the number of vertices in the graph $G$ and $v_1(G)$ be the number of vertices of degree 1 in $G$. We prove that if $G$ has no isolated vertices, then $\tilde{r}(P_7,G)\ge 8v(G)/5-v_1(G)$, $\tilde{r}(P_8,G)\ge 18v(G)/11-v_1(G)$ and $\tilde{r}(P_9,G)\ge 5v(G)/3-v_1(G)$. In particular $\tilde{r}(P_9,P_n)\ge 5n/3-2,$ which with known upper bound implies $\lim_{n\to\infty} \tilde{r}(P_9,P_n)/n=5/3.$ We also show that for any fixed $k$, $\lim_{n\to\infty} \tilde{r}(P_k,P_n)/n$ exists.

Institutions

Publication Details

Journal
ArXiv.org
Published
2025-04-21
Primary Topic
Data Mining and Machine Learning Applications
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Lower bounds for online size Ramsey numbers for paths

ArXiv.org
Data Mining and Machine Learning Applications
article

Lower bounds for online size Ramsey numbers for paths

article en

Abstract

Given two graphs $H_1$ and $H_2$, an online Ramsey game is played on the edge set of $K_\mathbb{N}$. In every round Builder selects an edge and Painter colors it red or blue. Builder is trying to force Painter to create a red copy of $H_1$ or a blue copy of $H_2$ as soon as possible, while Painter's goal is the opposite. The online (size) Ramsey number $\tilde{r}(H_1,H_2)$ is the smallest number of rounds in the game provided Builder and Painter play optimally. Let $v(G)$ be the number of vertices in the graph $G$ and $v_1(G)$ be the number of vertices of degree 1 in $G$. We prove that if $G$ has no isolated vertices, then $\tilde{r}(P_7,G)\ge 8v(G)/5-v_1(G)$, $\tilde{r}(P_8,G)\ge 18v(G)/11-v_1(G)$ and $\tilde{r}(P_9,G)\ge 5v(G)/3-v_1(G)$. In particular $\tilde{r}(P_9,P_n)\ge 5n/3-2,$ which with known upper bound implies $\lim_{n\to\infty} \tilde{r}(P_9,P_n)/n=5/3.$ We also show that for any fixed $k$, $\lim_{n\to\infty} \tilde{r}(P_k,P_n)/n$ exists.

ArXiv.org
Adam Mickiewicz University in Poznań (PL)
Openalex Percentile: Top 37%
Data Mining and Machine Learning Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Lower bounds for online size Ramsey numbers for paths · ArXiv.org (2025) | TGRS Research Map | TGRS