Cliques are Ramseyextremal
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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, 515527, NorthHolland,
Amsterdam, 1975.

2 
P. Erdös, On some problems in graph theory, combinatorial
analysis and combinatorial number theory, Graph theory and
combinatorics (Cambridge, 1983), 117, Academic Press,
LondonNew York, 1984.
