کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777141 1632570 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Junta Method in Extremal Hypergraph Theory and Chvátal's Conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Junta Method in Extremal Hypergraph Theory and Chvátal's Conjecture
چکیده انگلیسی

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an 'enlarged' copy H+ of a fixed hypergraph H. These include well-known open problems such as the Erdős matching conjecture, the Erdős-Sós 'forbidding one intersection' problem, the Frankl-Füredi 'special simplex' problem, etc.We present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove that any H+-free hypergraph is essentially contained in a 'junta' - a hypergraph determined by a small number of vertices - that is also H+-free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all Cn0(d).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 711-717
نویسندگان
, ,