Premium
Ramsey numbers of sparse hypergraphs
Author(s) -
Conlon David,
Fox Jacob,
Sudakov Benny
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20260
Subject(s) - hypergraph , ackermann function , mathematical proof , combinatorics , mathematics , ramsey's theorem , constant (computer programming) , upper and lower bounds , bounded function , discrete mathematics , ramsey theory , computer science , graph , mathematical analysis , inverse , geometry , programming language
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,$$ c (\Delta, k) \leq 2^{2^{.^{.^{.^{2^{2\Delta ,$$ 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. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009