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.
Submitted - 0710.0027.pdf