# $$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.