3-Uniform hypergraphs of bounded degree have linear Ramsey numbers
Research output: Contribution to journal › Article
Colleges, School and Institutes
Chvatal, Rodl, Szemeredi and Trotter [V. Chvatal, V. Rodl, E. Szemeredi, W.T. Trotter Jr., The Ramsey number of a graph with a bounded maximum degree, J. Combin. Theory Ser. B 34 (1983) 239-243] 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. (c) 2007 Elsevier Inc. All rights reserved.
|Number of pages||22|
|Journal||Journal of Combinatorial Theory. Series B|
|Publication status||Published - 1 May 2008|
- embedding problems, Ramsey numbers, hypergraphs, regularity lemma