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 August 2009 | Submitted
Journal Article Open

Ramsey numbers of sparse hypergraphs


We give a short proof that any k‐uniform hypergraph H on n vertices with bounded degree Δ has Ramsey number at most c(Δ,k)n, for an appropriate constant c(Δ,k). This result was recently proved by several authors, but those proofs are all based on applications of the hypergraph regularity method. Here we give a much simpler, self‐contained proof which uses new techniques developed recently by the authors together with an argument of Kostochka and Rödl. Moreover, our method demonstrates that, for k ≥ 4, [equation; see abstract in PDF for details], where the tower is of height k and the constant c depends on k. It significantly improves on the Ackermann‐type upper bound that arises from the regularity proofs, and we present a construction which shows that, at least in certain cases, this bound is not far from best possible. Our methods also allows us to prove quite sharp results on the Ramsey number of hypergraphs with at most m edges.

Additional Information

© 2008 Wiley. Issue online 15 June 2009; version of record online 17 December 2008; manuscript accepted 07 May 2008; manuscript received 27 September 2007. Fox research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Sudakov research supported in part by NSF CAREER award DMS-0546523, NSF grants DMS-0355497 and DMS-0635607, by a USA-Israeli BSF grant, and by the State of New Jersey. We would like to thank Jan Hladky for finding several typos in an earlier version of this paper.

Attached Files

Submitted - 0710.0027.pdf


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

Additional details

August 21, 2023
October 18, 2023