$P_n$和$C_n^k$的Ramsey数

称Fk为图F的k幂次图,如果V(Fk)=V(F),且Fk中的任意两个顶点相邻当且仅当在F中的距离至多为k.给定图G和H,Ramsey数R(G,H)为最小的正整数N,使得完全图KN的任意红蓝-边着色都会含有一个红色的子图G或者蓝色的子图H.证明了渐近阶R(Pn,Ckn)=(n-1)(χ(Ckn)-1)+σ(Ckn)+o(n),其中k是常数.

Ramsey number of a path and $C_n^k$

Define the $k$-th power $F_k$ of a graph $F$ as a graph on $V (F)$, in which two vertices are adjacent if their distance in $F$ is at most $k$. Given graphs $G$ and $H$, Ramsey number $R(G,H)$ is the smallest integer $N$ such that any red-blue edge-coloring of $K_N$ contains a red copy of $G$ or a blue copy of $H$. Recently, Pokrovskiy proved that $R(P_n,P_n^k)=(n-1)k \lfloor \frac{n}{k 1}\rfloor$, which solves a conjecture of Allen, Brightwell and Skokan. In this paper, we show that $R(P_n,C_n^k)=(n-1)(\chi(C_n^k)-1) \sigma(C_n^k) o(n)$ holds for fixed $k$ and $n\to \infty$.