The Junta Method for Hypergraphs

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

• Noam Lifschitz (Bar-Ilan University)
• Thursday 31 May 2018, 14:30-15:30
• MR13.

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.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR13
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.