Exact values for Ramsey numbers for \(k\)-cycle
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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
For the upper bound, it is known [1] that for even \( k=2m\), we have
For odd \( k=2m+1\), it is known that [2]
Erdos, Faudree, Rousseau, Schelp [3] proposed the following three problems:
Problem:
Is it true that for \(n>3\), \begin{equation}r(C_k, K_n) = (k-1)(n-1)+1 \end{equation} 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].