3-uniform hypergraphs of bounded degree have linear Ramsey numbers (Q2483473): Difference between revisions

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.