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 June 2013 | Submitted
Journal Article Open

The Ramsey number of dense graphs


The Ramsey number r(H) of a graph H is the smallest number n such that, in any two-colouring of the edges of K_n, there is a monochromatic copy of H. We study the Ramsey number of graphs H with t vertices and density ρ, proving that r(H) ≤ 2^(c√(ρ)log(2/ρ)t). We also investigate some related problems, such as the Ramsey number of graphs with t vertices and maximum degree ρt and the Ramsey number of random graphs in G(t, ρ), that is, graphs on t vertices where each edge has been chosen independently with probability ρ.

Additional Information

© 2012 London Mathematical Society. Received 15 July 2009; revised 16 August 2012; published online 20 December 2012. This research was supported by a research fellowship at St John's College, Cambridge.

Attached Files

Submitted - 0907.2657.pdf


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

Additional details

August 19, 2023
October 18, 2023