Upper bound for Ramsey number for \(4\)cycle
Home
Search
Subjects
About Erdös
About This Site
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. The classical Ramsey numbers are those for the complete graphs and are denoted by \( r(s,t)= r(K_s, K_t)\).
Erdös posed the following conjecture at the International Congress of Mathematicians in Warsaw in 1983.
Conjecture [1] For some \(\epsilon > 0\), \[ r(C_4, K_n) = o(n^{2\epsilon}). \]
It is known that
\(\displaystyle c(\frac{n}{\log n} )^2 > r(C_4,K_n) > c(\frac{n}{\log n} )^{3/2}, \)
where the lower bound is proved by probabilistic methods [2], and the upper
bound is due to Szemerédi (an unpublished result mentioned in [3]).
Bibliography  

1 
P. Erdös, Extremal problems in number theory, combinatorics and
geometry, Proceedings of the International Congress of
Mathematicians, Vol. 1, 2 (Warsaw, 1983), 5170, PWN, Warsaw, 1984.

2 
J. Spencer, Asymptotic lower bounds for Ramsey functions,
Discrete Math. 20 (1977/78), 6976.

3 
P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp,
On cyclecomplete graph Ramsey numbers, J. Graph
Theory 2 (1978), 5364.
