An upper bound for Ramsey numbers. (Q1764577): Difference between revisions

The Ramsey number, \(r(G,H)\) of the graphs \(G\) and \(H\) is the smallest integer \(N\) such that every colouring of the edges of \(K_N\) with red and blue yields either a red \(G\) or a blue \(H\). The Erdős-Szekeres recursion theorem yields \(r(G,H)\leq r(G',H)+r(G,H')\), where \(G'\) is a graph obtained by deleting one vertex from \(G\). This paper goes one step further, and works with \(G''\) and \(H''\), where two vertices have been deleted. Let \(A=r(G'',H)\) and \(B=r(G,H'')\), then the result is: \(r(G,H)\leq A+B+2+2\sqrt{(A^2+AB+B^2)/3}\).