Published November 2009
| Version 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
Identifiers
- Eprint ID
- 97831
- Resolver ID
- CaltechAUTHORS:20190812-162959718
Funding
- St. John's College, Cambridge
Dates
- Created
-
2019-08-15Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Mathematics Department