Ramsey numbers of sparse hypergraphs

Abstract

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.

Files

Additional details