3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Oliver Cooley; Nikolaos Fountoulakis; Daniela Kuhn; Deryk Osthus

doi:10.1016/j.jctb.2007.08.008

3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Oliver Cooley, Nikolaos Fountoulakis, Daniela Kuhn, Deryk Osthus

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	484-505
Number of pages	22
Journal	Journal of Combinatorial Theory. Series B
Volume	98
Issue number	3
DOIs	https://doi.org/10.1016/j.jctb.2007.08.008
Publication status	Published - 1 May 2008

Keywords

embedding problems
Ramsey numbers
hypergraphs
regularity lemma

Access to Document

10.1016/j.jctb.2007.08.008

Probabilistic Methods in Graph Theory
Kuhn, D. (Principal Investigator) & Osthus, D. (Co-Investigator)
Engineering & Physical Science Research Council
26/04/06 → 25/01/09
Project: Research Councils

Cite this

@article{0ec24125957d4eb19d75951ad07cf0ef,

title = "3-Uniform hypergraphs of bounded degree have linear Ramsey numbers",

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.",

keywords = "embedding problems, Ramsey numbers, hypergraphs, regularity lemma",

author = "Oliver Cooley and Nikolaos Fountoulakis and Daniela Kuhn and Deryk Osthus",

year = "2008",

month = may,

day = "1",

doi = "10.1016/j.jctb.2007.08.008",

language = "English",

volume = "98",

pages = "484--505",

journal = "Journal of Combinatorial Theory. Series B",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - 3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

AU - Cooley, Oliver

AU - Fountoulakis, Nikolaos

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2008/5/1

Y1 - 2008/5/1

N2 - 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.

AB - 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.

KW - embedding problems

KW - Ramsey numbers

KW - hypergraphs

KW - regularity lemma

U2 - 10.1016/j.jctb.2007.08.008

DO - 10.1016/j.jctb.2007.08.008

M3 - Article

VL - 98

SP - 484

EP - 505

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 3

ER -

3-Uniform hypergraphs of bounded degree have linear Ramsey numbers

Abstract

Keywords

Access to Document

Fingerprint

Projects

Probabilistic Methods in Graph Theory

Cite this