Ramsey numbers of sparse hypergraphs

Ramsey numbers of sparse hypergraphs,10.1002/rsa.20260,Random Structures and Algorithms,David Conlon,Jacob Fox,Benny Sudakov

Ramsey numbers of sparse hypergraphs   (Citations: 6)
BibTex | RIS | RefWorks Download
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 Rodl. Moreover, our method demonstrates that, for k ≥ 4, c(�, k) ≤ 22 . . .2 c�
Journal: Random Structures and Algorithms - RSA , vol. 35, no. 1, pp. 1-14, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Indeed, in [6], we found a 3-uniform hypergraph Cn on n vertices which is much sparser than the complete hypergraph K (3) n and whose four-color Ramsey number satisfies r(Cn;4) > 2 2...

    David Conlonet al. Hypergraph Ramsey numbers

    • ...has maximum degree at most �. After this manuscript was submitted, Conlon, Fox and Sudakov [4] obtained a proof of Theorem 1 which does not rely on hypergraph regularity and gives a better bound on C. Also, Ishigami [16] independently announced a proof of Theorem 1 using a similar approach to ours...

    Oliver Cooleyet al. Embeddings and Ramsey numbers of sparse kappa-uniform hypergraphs

    • ...Indeed, in [3], the author, together with Fox and Sudakov, has shown that there are 3-uniform hypergraphs on n vertices whose density tends to zero as n gets large but whose 4-colour Ramsey number is at least 22...

    David Conlon. The Ramsey number of dense graphs

Sort by: