Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2012 | Submitted
Journal Article Open

On two problems in graph Ramsey theory


We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K_N contains a monochromatic copy of H. A famous result of Chvátal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c' such that 2^(c'Δ) ≤ c(Δ) ≤ c^(Δlog^(2)Δ). We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2^(cΔlogΔ).

Additional Information

© 2012 János Bolyai Mathematical Society and Springer-Verlag. Received 29 January 2010; first online 04 October 2012. Conlon research supported by a Junior Research Fellowship at St John's College. Fox research supported by a Simons Fellowship, an MIT NEC Corp. award and NSF grant DMS-1069197. Sudakov research supported in part by NSF grant DMS-1101185, by AFOSR MURI grant FA9550-10-1-0569 and by a USA-Israel BSF grant.

Attached Files

Submitted - 1002.0045.pdf


Files (232.6 kB)
Name Size Download all
232.6 kB Preview Download

Additional details

August 19, 2023
October 18, 2023