Embedding tetrahedra into quasirandom hypergraphs

作者：Reiher Christian^*; Rodl Vojtech; Schacht Mathias

来源：Journal of Combinatorial Theory - Series B, 2016, 121: 229-247.

DOI：10.1016/j.jctb.2016.06.008

• Quasirandom hypergraphs
• Extremal graph theory
• Turan's problem
• Tetrahedron

We investigate extremal problems for quasirandom hypergraphs. We say that a 3-uniform hypergraph H = (V, E) is (d,77,therefore)-quasirandom if for any subset X subset of V and every set of pairs P subset of V x V the number of pairs (n, (y, z)) is an element of X x P with {z,y,z} being a hyperedge of H is in the interval d vertical bar X vertical bar vertical bar P vertical bar +/- eta vertical bar V vertical bar(3). We show that for any epsilon > 0 there exists eta > 0 such that every sufficiently large (1/2 + epsilon,eta,therefore)-quasirandom hypergraph containg a tetrahedron, i.e., four vertices spanning all four hyperedges. A known random construction shows that the density 1/2 is best possible. This result is closely related to a question of Erdos, whether every weakly quasirandom 3-uniform hypergraph H with density bigger than 1/2, i.e., every large subset of vertices induces a hypergraph with density bigger than 1/2, contains a tetrahedron.

• 出版日期2016-11