Upper bound for Ramsey number for \(4\)-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. 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), 51-70, PWN, Warsaw, 1984.

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

3 P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp, On cycle-complete graph Ramsey numbers, J. Graph Theory 2 (1978), 53-64.