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\).

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.