# Exact values for Ramsey numbers for $$k$$-cycle

For two graphs $$G$$ and $$H$$, let $$r(G,H)$$ denote the smallest integer $$m$$ satisfying the property that if the edges of the complete graph $$K_m$$ are colored in red and blue, then there is either a subgraph isomorphic to $$G$$ with all red edges or a subgraph isomorphic to $$H$$ with all blue edges. Here we consider the cycle-complete graph Ramsey number, $$r(C_k, K_n)$$.

For $$k$$ fixed and $$n$$ large, the probabilistic method gives

$$\displaystyle r(C_k,K_n) > c (n/\log n)^{(k-1)/(k-2)}.$$

For the upper bound, it is known [1] that for even $$k=2m$$, we have

$$\displaystyle r(C_{2m},K_n) \leq c_m (n / \log n)^{m/(m-1)}.$$

For odd $$k=2m+1$$, it is known that [2]

$$\displaystyle r(C_{2m+1}, K_n)\leq c_m\frac{n^{1+1/m}}{\log^{1/m}n}.$$

Erdos, Faudree, Rousseau, Schelp [3] proposed the following three problems:

# Problem:

Is it true that for $$n>3$$, $$r(C_k, K_n) = (k-1)(n-1)+1$$ if $$k \geq n$$?

# Problem:

What is the smallest value of $$k$$ such that $$r(C_k, K_n) = (k-1)(n-1)+1$$?

# Problem:

For a fixed $$n$$, what is the minimum value of $$r(C_k,K_n)$$ over all $$k$$?

For $$C_{k}$$, with $$k>n^2-2$$, the result (1) was proven in 1973 by Bondy and Erdos [4]. In 2005, Nikiforov [5] proved (1) also holds for $$k\geq 4n+2$$. Moreover, the result has been proven for $$n=3, 4, 5,$$ and $$6$$ (with the exception of $$r(C_3, K_3)=6$$) [6][7][8][9][10].