Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Peter Keevash

School of Mathematical Sciences \\ Queen Mary, University of London

A hypergraph regularity method for generalised Turan problems

Abstract:

We introduce a new method for analysing certain problems in extremal combinatorics that involve small forbidden configurations. The cornerstone of our approach is a quasirandom counting lemma for quasirandom hypergraphs, which extends the standard counting lemma by not only counting copies of any particular configuration but also showing that these copies are evenly distributed. We demonstrate the power of the method by proving a conjecture of Mubayi on the codegree threshold of the Fano plane, that any 3-graph on n vertices for which every pair of vertices is contained in more than $n/2$ edges must contain a Fano plane, for n sufficiently large. For projective planes over fields of odd size we show that the codegree threshold is between $n/2-q+1$ and $n/2$, but for $PG_2(4)$ we find the somewhat surprising phenomenon that the threshold is less than $(1/2-c)n$ for some absolute $c>0$.

Host: Jeff Remmel

December 4, 2007

3:00 PM

AP&M 7321

****************************