P_n 和C_n^k的 Ramsey数

Ramsey number of a path and C_n^k

称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是常数.

Define the kth power Fk 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 KN contains a red copy of G or a blue copy of H. We show that R（Pn, Cnk） = （n - 1） （X （Cnk） -- 1） ＋ a （ Cnk ） ＋ o （n） holds for fixed k and large n.