کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777141 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |

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 C
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 711-717