کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656659 1632972 2016 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Embedding tetrahedra into quasirandom hypergraphs
ترجمه فارسی عنوان
تثبیت کردن تتراهداها به ابرگرافهای سه بعدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 121, November 2016, Pages 229–247
نویسندگان
, , ,