University of Cambridge > Talks.cam > Combinatorics Seminar > The Junta Method for Hypergraphs

The Junta Method for Hypergraphs

Add to your list(s) Download to your calendar using vCal

  • UserNoam Lifschitz (Bar-Ilan University)
  • ClockThursday 31 May 2018, 14:30-15:30
  • HouseMR13.

If you have a question about this talk, please contact Andrew Thomason.

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 Erdős ‘forbidding one intersection’ problem and the Frankl-Füredi ‘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 k in the range C to 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.

Based on joint works with David Ellis and Nathan Keller

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity