The Junta Method for Hypergraphs

Speaker
Nathan Keller, Bar-Ilan University
Date
08/04/2018 - 13:00 - 12:00Add to Calendar 2018-04-08 12:00:00 2018-04-08 13:00:00 The Junta Method for Hypergraphs 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  problems such as the Erdos-Sos 'forbidding one intersection' problem and the Frankl-Furedi 'special simplex' problem.     In this talk 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<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes  the aforementioned problems, and solves them for a large new set of parameters. Joint work with Noam Lifshitz.     Mathematics Colloquium Room 201, Bldg. 216 אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Mathematics Colloquium Room 201, Bldg. 216
Abstract
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  problems such as the Erdos-Sos 'forbidding one intersection' problem and the Frankl-Furedi 'special simplex' problem.  
 
In this talk 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<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes  the aforementioned problems, and solves them for a large new set of parameters. Joint work with Noam Lifshitz.
 
 

תאריך עדכון אחרון : 25/03/2018