3-uniform hypergraphs of bounded degree have linear Ramsey numbers

DOI10.1016/J.JCTB.2007.08.008MaRDI QIDQ2483473zbMATH OpenOpenAlexFDO

Authors Oliver Cooley, Nikolaos Fountoulakis, Deryk Osthus, Daniela Kühn

Publication date 28 April 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0608442

zbMATH Keywords

embedding problemshypergraphsRamsey numbersregularity Lemma

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65)

Abstract: Chv'atal, R"odl, Szemer'edi 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.

Recommendations

• Linear Ramsey Numbers for Bounded-Degree Hypergrahps
• Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
• Ramsey numbers of sparse hypergraphs
• On the Ramsey number of sparse 3-graphs
• The Ramsey number of a graph with bounded maximum degree

Cites work

• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Extremal problems on set systems
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Integer and fractional packings in dense 3‐uniform hypergraphs
• Linear Ramsey Numbers for Bounded-Degree Hypergrahps
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Note on the 3-graph counting Lemma
• On Ramsey numbers of uniform hypergraphs with given maximum degree
• On the Ramsey number of sparse 3-graphs
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Regular Partitions of Hypergraphs: Counting Lemmas
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regularity properties for triple systems
• The Ramsey number for hypergraph cycles. I.
• The Ramsey number of a graph with bounded maximum degree
• The counting lemma for regular k‐uniform hypergraphs

Cited in

(19)

• Ramsey numbers of 3-uniform loose paths and loose cycles
• On the Ramsey number of sparse 3-graphs
• On the size of 3-uniform linear hypergraphs
• Dependent random choice
• The Ramsey number of Fano plane versus tight path
• Monochromatic loose-cycle partitions in hypergraphs
• On Ramsey numbers of uniform hypergraphs with given maximum degree
• Monochromatic bounded degree subgraph partitions
• Big Ramsey degrees of 3-uniform hypergraphs
• On two problems in graph Ramsey theory
• On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs
• Ramsey numbers of sparse hypergraphs
• Diagonal Ramsey numbers of loose cycles in uniform hypergraphs
• Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
• Constructive Packings of Triple Systems
• Linear Ramsey Numbers for Bounded-Degree Hypergrahps
• Ramsey numbers of sparse hypergraphs
• The Ramsey number for 3-uniform tight hypergraph cycles
• Big Ramsey degrees of 3-uniform hypergraphs are finite

This page was built for publication: 3-uniform hypergraphs of bounded degree have linear Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483473)