Premium
A hypergraph regularity method for generalized Turán problems
Author(s) -
Keevash Peter
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20249
Subject(s) - lemma (botany) , hypergraph , fano plane , conjecture , combinatorics , mathematics , plane (geometry) , graph , discrete mathematics , projective plane , pure mathematics , geometry , ecology , poaceae , correlation , biology
We describe a method that we believe may be foundational for a comprehensive theory of generalized Turán problems. 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 a 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 is, 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 q 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 − ϵ) n for some small ϵ > 0. We conclude by setting out a program for future developments of this method to tackle other problems. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009