A conjecture of Erdős on graph Ramsey numbers (Q531812): Difference between revisions

The Ramsey number \(r(G)\) of a graph \(G\) is the minimum \(N\) such that every red-blue coloring of the edges of the complete graph on \(N\) vertices contains a monochromatic copy of \(G\). Confirming old conjecture of Erdős, the author proves that \(r(G)\leqslant 2^{250\sqrt{m}}\) for any graphs on \(m\) edges with no isolated vertices. The proof uses some hard density arguments. In the introduction, the author outlines the history of the conjecture.