کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656659 | 1632972 | 2016 | 19 صفحه PDF | دانلود رایگان |
We investigate extremal problems for quasirandom hypergraphs. We say that a 3-uniform hypergraph H=(V,E)H=(V,E) is (d,η,)(d,η,)-quasirandom if for any subset X⊆VX⊆V and every set of pairs P⊆V×VP⊆V×V the number of pairs (x,(y,z))∈X×P(x,(y,z))∈X×P with {x,y,z}{x,y,z} being a hyperedge of H is in the interval d|X||P|±η|V|3. We show that for any ε>0ε>0 there exists η>0η>0 such that every sufficiently large (1/2+ε,η,)(1/2+ε,η,)-quasirandom hypergraph contains 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 Erdős, 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.
Journal: Journal of Combinatorial Theory, Series B - Volume 121, November 2016, Pages 229–247