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.

Review text

From an old theorem of \textit{C. Chvatál, V. Rödl, E. Szemerédi} and \textit{W. T. Trotter jun.} [J. Comb. Theory, Ser. B 34, No. 3, 239--243 (1983; Zbl 0547.05044)] it is known that the Ramsey number of a graph with bounded degrees is linear in its order. The original proof used Szemerédi's regularity lemma and the so called ``embedding lemma. The paper under review generalizes their result (and proof) analogously for bounded degree 3-uniform hypergraphs. The main tool for that is an analogue of the regularity lemma for 3-uniform hypergraphs (due to Frankl and Rödl) and a suitable ``embedding of sparse 3-uniform hypergraphs into ``pseudo-random hypergraphs. This new result requires extra attention and a complicated proof.

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

• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Extremal problems on set systems
• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• 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 counting lemma for regular k‐uniform hypergraphs
• The Ramsey number for hypergraph cycles. I.
• The Ramsey number of a graph with bounded maximum degree

Cited in

(20)

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

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)