3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

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.

Details

Original languageEnglish
Pages (from-to)484-505
Number of pages22
JournalJournal of Combinatorial Theory. Series B
Volume98
Issue number3
Publication statusPublished - 1 May 2008

Keywords

  • embedding problems, Ramsey numbers, hypergraphs, regularity lemma