3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)484-505
Number of pages22
JournalJournal of Combinatorial Theory. Series B
Volume98
Issue number3
DOIs
Publication statusPublished - 1 May 2008

Keywords

  • embedding problems
  • Ramsey numbers
  • hypergraphs
  • regularity lemma

Fingerprint

Dive into the research topics of '3-Uniform hypergraphs of bounded degree have linear Ramsey numbers'. Together they form a unique fingerprint.

Cite this