Embedding tetrahedra into quasirandom hypergraphs
Embedding tetrahedra into quasirandom hypergraphs
复制标题
DOI：
10.1016/j.jctb.2016.06.008
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Christian Reiher;V. Rödl;M. Schacht
中科院分区：
文献类型：
--
作者：
Christian Reiher;V. Rödl;M. Schacht
我们研究拟随机超图的极值问题。我们称3-一致超图H=(V，E)是(d，η，)-随机的，如果对任何子集X⊆V和每一对P⊆V×V，具有{x，y，z}为H的超边的(x，(y，z))∈X×P的对数在区间d|X||P|±η|V|3中。我们证明了对于任何ε>；0，都存在η>；0使得每个足够大的(1/2+ε，η，)-拟随机超图包含一个四面体，即横跨所有四条超边的四个顶点。一个已知的随机结构表明，密度为1/2是最好的可能。这一结果与ErdőS提出的一个问题密切相关，即每个密度大于1/2的弱拟随机3一致超图H是否包含一个四面体。
We investigate extremal problems for quasirandom hypergraphs. We say that a 3-uniform hypergraph H=(V, E) is (d, η,)-quasirandom if for any subset X⊆ V and every set of pairs P⊆ V× V the number of pairs (x,(y, z))∈ X× P with {x, y, z} being a hyperedge of H is in the interval d| X|| P|±η| V| 3. We show that for any ε> 0 there exists η> 0 such that every sufficiently large (1/2+ ε, η,)-quasirandom hypergraph contains a tetrahedron, ie, 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 Erdős, whether every weakly quasirandom 3-uniform hypergraph H with density bigger than 1/2, ie, every large subset of vertices induces a hypergraph with density bigger than 1/2, contains a tetrahedron.