***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Nathan Keller, Bar Ilan University

Thursday 27th February, 3:00 in Fine Hall 224.

Title: 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.

		----------------------------------

Next week: Frantisek Kardos

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)