Mathematics – Combinatorics
Scientific paper
2007-09-29
Mathematics
Combinatorics
13 pages
Scientific paper
We give a short proof that any k-uniform hypergraph H on n vertices with bounded degree \Delta has Ramsey number at most c(\Delta, k)n, for an appropriate constant c(\Delta, 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\"odl. Moreover, our method demonstrates that, for k \geq 4, c(\Delta, k) \leq 2^{2^{\Ddots^{2^{c \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.
Conlon David
Fox Jacob
Sudakov Benny
No associations
LandOfFree
Ramsey numbers of sparse hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Ramsey numbers of sparse hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ramsey numbers of sparse hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-461893