3-uniform hypergraphs of bounded degree have linear Ramsey numbers (Q2483473)

From MaRDI portal
Revision as of 20:46, 10 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
3-uniform hypergraphs of bounded degree have linear Ramsey numbers
scientific article

    Statements

    3-uniform hypergraphs of bounded degree have linear Ramsey numbers (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    28 April 2008
    0 references
    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.
    0 references
    hypergraphs
    0 references
    regularity Lemma
    0 references
    Ramsey numbers
    0 references
    embedding problems
    0 references

    Identifiers