\(r(G)\) is subexponential in sqrt(edges)

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)\). If \( s=t\), we write \( r(s)=r(s, s)\).

The following several problems run along the lines of attempting to clarify the relationship between graph Ramsey numbers and the classical ones. Although these problems [1] [2] were raised very early on, little progress has been made so far.

Problem [2]

Is it true that if a graph \(G\) has \(e\) edges, then \[ r(G) < 2^{c e ^{1/2}} \] for some absolute constant \(c\)?

Bibliography
1 P. Erdös and R. L. Graham, On partition theorems for finite graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdös on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 515-527, North-Holland, Amsterdam, 1975.

2 P. Erdös, On some problems in graph theory, combinatorial analysis and combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983), 1-17, Academic Press, London-New York, 1984.