A hypergraph regularity method for generalized Turán problems

DOI10.1002/RSA.20249zbMATH Open1182.05125arXiv0809.3674OpenAlexW4256532737MaRDI QIDQ3608316FDOQ3608316

Authors: Peter Keevash 

Publication date: 4 March 2009

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

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.

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

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

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)

Cites Work

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

Cited In (15)

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

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)