3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Abstract

Chvátal, Rödl, Szemerédi and Trotter proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. We prove that the same holds for 3-uniform hypergraphs. The main new tool which we prove and use is an embedding lemma for 3-uniform hypergraphs of bounded maximum degree into suitable 3-uniform `pseudo-random' hypergraphs.

19 pages, 1 figure, submitted to J. Comb. Theory Ser. B

References in corpus (1)

• Hypergraph regularity and the multidimensional Szemerédi theorem

Cited by in corpus (2)

• Linear Ramsey numbers for bounded-degree hypergraphs
• The number of hypergraphs and colored Hypergraphs with hereditary properties