A conjecture of Erdős on graph Ramsey numbers (Q531812): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Igor Vladimirov Protasov / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C55 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5880835 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ramsey numbers | |||
Property / zbMATH Keywords: Ramsey numbers / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Erdős' conjecture | |||
Property / zbMATH Keywords: Erdős' conjecture / rank | |||
Normal rank |
Revision as of 09:01, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A conjecture of Erdős on graph Ramsey numbers |
scientific article |
Statements
A conjecture of Erdős on graph Ramsey numbers (English)
0 references
20 April 2011
0 references
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.
0 references
Ramsey numbers
0 references
Erdős' conjecture
0 references