A hypergraph regularity method for generalized Turán problems

DOI10.1002/RSA.20249MaRDI QIDQ3608316zbMATH OpenOpenAlexFDO

Authors Peter Keevash

Publication date 4 March 2009

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.3674

zbMATH Keywords

extremal combinatoricshypergraphsquasirandom hypergraphsFano planehypergraph regularityquasirandom counting lemma

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorial structures in finite projective spaces (51E20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We describe a method that we believe may be foundational for a comprehensive theory of generalised Turan 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 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-c)n for some small c>0. We conclude by setting out a program for future developments of this method to tackle other problems.

Recommendations

• On a Turán problem in weakly quasirandom 3-uniform hypergraphs
• scientific article; zbMATH DE number 5942358
• The Turán problem for projective geometries
• Applications of the regularity lemma for uniform hypergraphs
• The hypergraph regularity method and its applications

Cites work

• scientific article; zbMATH DE number 4052438 (Why is no real title available?)
• scientific article; zbMATH DE number 4080277 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1101474 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A variant of the hypergraph removal lemma
• Co-degree density of hypergraphs
• Codegree problems for projective geometries
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Limits of dense graph sequences
• On a hypergraph Turán problem of Frankl
• Quasi-random graphs
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regularity Lemma for k-uniform hypergraphs
• Set systems without a simplex or a cluster
• The Turán problem for projective geometries
• The co-degree density of the Fano plane
• The maximum size of 3-uniform hypergraphs not containing a Fano plane
• The primes contain arbitrarily long arithmetic progressions
• Triple Systems Not Containing a Fano Configuration

Cited in

(14)

• The codegree threshold for 3-graphs with independent neighborhoods
• On the Chromatic Thresholds of Hypergraphs
• On the codegree density of complete 3-graphs and related problems
• Counting Steiner triple systems
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• The poset of hypergraph quasirandomness
• On the codegree density of \(\mathrm{PG}_m(q)\)
• Eigenvalues and linear quasirandom hypergraphs
• A hypergraph blow-up lemma
• Codegree Turán density of complete \(r\)-uniform hypergraphs
• Codegree thresholds for covering 3-uniform hypergraphs
• Hypergraphs with independent neighborhoods
• On the co-degree threshold for the Fano plane

This page was built for publication: A hypergraph regularity method for generalized Turán problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608316)