# Cliques are Ramsey-extremal

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.

# Conjecture (proposed by Erdös and Graham [1])

If $$G$$ has $$\binom{n}{2}$$ edges for $$n \geq 4$$, then $r(G) \leq r(n).$ More generally, if $$G$$ has $$\binom{n}{2}+t$$ edges, then $r(G) \leq r(H)$ where $$H$$ denotes the graph formed by connecting a new vertex to $$t$$ of the vertices of a $$K_n$$, and $$t \leq n$$.

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.