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 November 2009 | public
Journal Article

Hypergraph Packing and Sparse Bipartite Ramsey Numbers

Abstract

We prove that there exists a constant c such that, for any integer Δ, the Ramsey number of a bipartite graph on n vertices with maximum degree Δ is less than 2^(cΔ)n. A probabilistic argument due to Graham, Rödl and Ruciński implies that this result is essentially sharp, up to the constant c in the exponent. Our proof hinges upon a quantitative form of a hypergraph packing result of Rödl, Ruciński and Taraz.

Additional Information

© Cambridge University Press 2009. Received 30 July 2007; revised 24 April 2009; first published online 22 June 2009. The author is kindly supported by a grant from St John's College, Cambridge. I would like to thank the referee for several helpful comments.

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023