A conjecture of Erdős on graph Ramsey numbers
详细信息 查看全文
- 作者：Benny Sudakov<sup>1sup><sup> ; sup><sup>asup><sup> ; sup><sup>bsudakov@math.ucla.edusup>
- 关键词：Ramsey numbers ; Erdő ; s
src=""http ; //www.sciencedirect.com/scidirimg/entities/2bc.gif"" alt=""modifier letter apostrophe"" title=""modifier letter apostrophe"" border=""0""> conjecture
- 刊名：Advances in Mathematics
- 出版年：2011
- 出版时间：1 May 2011
- 年：2011
- 卷：227
- 期：1
- 页码：601-609
- 全文大小：119 K
文摘
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. Determining or estimating these numbers is one of the central problems in combinatorics.
One of the oldest results in Ramsey Theory, proved by Erdős and Szekeres in 1935, asserts that the Ramsey number of the complete graph with m edges is at most . Motivated by this estimate Erdős conjectured, more than a quarter century ago, that there is an absolute constant c such that for any graph G with m edges and no isolated vertices. In this short note we prove this conjecture.