论文标题
在线大小拉姆齐号码：路径vs $ C_4 $
Online size Ramsey numbers: Path vs $C_4$
论文作者
论文摘要
给定两个图表$ g $和$ h $，在$ k_ \ mathbb {n} $的边缘集上播放了大小的ramsey游戏。在每一轮比赛中，建筑商都会选择一个边缘，画家将其颜色为红色或蓝色。建筑商的目标是强迫画家尽快创建$ g $的红色副本或$ h $的蓝色副本。在线（尺寸）Ramsey编号$ \ tilde r（g，h）$是游戏中提供的构建器和画家游戏中最佳播放的回合数。我们证明，每$ n \ ge 8 $，$ \ tilde r（C_4，P_N）\ le 2n-2 $。上限与J. Cyman，T。Dzido，J。Lapinskas和A. Lo获得的下限匹配，因此我们得到$ \ tilde r（C_4，P_N）= 2n-2 $ for $ n \ ge 8 $。我们的$ N \ le 13 $的证明是计算机协助的。绑定的$ \ tilde r（c_4，p_n）\ le 2n-2 $ solves solves也解决了$ n \ ge 8 $ - $的“所有循环vs. $ p_n $”游戏，这意味着需要$ 2N-2 $ rounds迫使画家在$ N $ dertices或任何红色周期上创建蓝色路径。
Given two graphs $G$ and $H$, a size Ramsey game is played on the edge set of $K_\mathbb{N}$. 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 $\tilde r(G,H)$ is the number of rounds in the game provided Builder and Painter play optimally. We prove that $\tilde r(C_4,P_n)\le 2n-2$ for every $n\ge 8$. The upper bound matches the lower bound obtained by J. Cyman, T. Dzido, J. Lapinskas, and A. Lo, so we get $\tilde r(C_4,P_n)=2n-2$ for $n\ge 8$. Our proof for $n\le 13$ is computer assisted. The bound $\tilde r(C_4,P_n)\le 2n-2$ solves also the "all cycles vs. $P_n$" game for $n\ge 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.
