Combinatorial theorems in sparse random sets

DOI10.4007/ANNALS.2016.184.2.2MaRDI QIDQ350550zbMATH OpenOpenAlexWikidataFDO

Authors David Conlon, W. Timothy Gowers

Publication date 7 December 2016

Published in Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.4310, https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957976

zbMATH Keywords

extremal combinatoricsrandom graphsrandom setssparse analogues

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Tur'an's theorem, Szemer'edi's theorem and Ramsey's theorem, hold almost surely inside sparse random sets. For instance, we extend Tur'an's theorem to the random setting by showing that for every $epsilon>0$ and every positive integer $tgeq3$ there exists a constant $C$ such that, if $G$ is a random graph on $n$ vertices where each edge is chosen independently with probability at least $C{n}^{-2/(t+1)}$, then, with probability tending to $1$ as $n$ tends to infinity, every subgraph of $G$ with at least $(1-frac1t-1+epsilon)e(G)$ edges contains a copy of $K_t$. This is sharp up to the constant $C$. We also show how to prove sparse analogues of structural results, giving two main applications, a stability version of the random Tur'an theorem stated above and a sparse hypergraph removal lemma. Many similar results have recently been obtained independently in a different way by Schacht and by Friedgut, R"odl and Schacht.

Recommendations

• Turán's theorem in sparse random graphs
• On \(K^ 4\)-free subgraphs of random graphs
• Turánnical hypergraphs
• Independent sets in hypergraphs
• Extremal results for random discrete structures

Cites work

• scientific article; zbMATH DE number 3523693 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 524135 (Why is no real title available?)
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A large deviation result on the number of small subgraphs of a random graph
• A new proof of Szemerédi's theorem
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• A variant of the hypergraph removal lemma
• An ergodic Szemerédi theorem for commuting transformations
• Arithmetic progressions of length three in subsets of a random set
• Arithmetic structures in random sets
• Combinatorial theorems relative to a random set
• Decompositions, approximate structure, transference, and the Hahn-Banach theorem
• Extremal results for random discrete structures
• Hypergraph containers
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Independent sets in hypergraphs
• K₅‐free subgraphs of random graphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Note on Combinatorial Analysis
• On Certain Sets of Integers
• On Certain Sets of Positive Density
• On Schur properties of random subsets of integers
• On Two-Point Configurations in a Random Set
• On \(K^ 4\)-free subgraphs of random graphs
• On the KŁR conjecture in random graphs
• Poisson approximation for large deviations
• Polynomial extensions of van der Waerden’s and Szemerédi’s theorems
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Rado Partition Theorem for Random Subsets of Integers
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• Ramsey properties of random discrete structures
• Ramsey properties of random graphs
• Ramsey properties of random hypergraphs
• Random Ramsey graphs for the four-cycle
• Random graphs with monochromatic triangles in every edge coloring
• Randomness and regularity
• Regularity Lemma for k-uniform hypergraphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Stability results for random discrete structures
• Supersaturated graphs and hypergraphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The Turn Theorem for Random Graphs
• The Turán number of the Fano plane
• The counting lemma for regular k‐uniform hypergraphs
• The deletion method for upper tail estimates
• The infamous upper tail
• The maximum size of 3-uniform hypergraphs not containing a Fano plane
• The primes contain arbitrarily long arithmetic progressions
• Threshold Functions for Ramsey Properties
• Triple Systems Not Containing a Fano Configuration
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Turán's theorem in sparse random graphs
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• Upper tails for subgraph counts in random graphs
• \(K_4\)-free subgraphs of random graphs revisited

Cited in

(only showing first 100 items - show all)

• On the stability of the Erdős-Ko-Rado theorem
• Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
• Turán's theorem in sparse random graphs
• Arcs in \(\mathbb{F}_q^2\)
• On the number of monotone sequences
• On the number of \(B_h\)-sets
• Stability results for random discrete structures
• Polynomial configurations in subsets of random and pseudo-random sets
• Counting sum-free sets in abelian groups
• Corrádi and Hajnal's theorem for sparse random graphs
• Counting independent sets in graphs
• Mantel's theorem for random hypergraphs
• The Turn Theorem for Random Graphs
• The number of \(C_{2\ell}\)-free graphs
• Solutions to certain linear equations in Piatetski-Shapiro sequences
• A probabilistic threshold for monochromatic arithmetic progressions
• On the KŁR conjecture in random graphs
• Partition regularity and the primes
• Counting configuration-free sets in groups
• Random differences in Szemerédi's theorem and related results
• On zero-sum free sequences contained in random subsets of finite cyclic groups
• Simple containers for simple hypergraphs
• Many \(T\) copies in \(H\)-free graphs
• Bandwidth theorem for random graphs
• An algorithmic framework for obtaining lower bounds for random Ramsey problems
• The typical structure of sparse \(K_{r+1}\)-free graphs
• A short proof of the random Ramsey theorem
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Independent sets in hypergraphs
• Spatially independent martingales, intersections, and applications
• On the cycle space of a random graph
• A multi-dimensional Szemerédi theorem for the primes via a correspondence principle
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• On an anti-Ramsey threshold for random graphs
• An exponential-type upper bound for Folkman numbers
• Infinite Sidon sets contained in sparse random sets of integers
• Roth's theorem in the Piatetski-Shapiro primes
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Symmetric and asymmetric Ramsey properties in random hypergraphs
• Ramsey games near the critical threshold
• Supersaturation in posets and applications involving the container method
• Extremal results in sparse pseudorandom graphs
• On Erdős-Ko-Rado for random hypergraphs. II
• On Erdős-Ko-Rado for random hypergraphs. I
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Extremal results in random graphs
• On two-point configurations in subsets of pseudo-random sets
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• A sharp threshold for van der Waerden's theorem in random subsets
• The number of \(K_{m,m}\)-free graphs
• Extremal results for random discrete structures
• Covering random graphs with monochromatic trees
• Dependent random choice
• A relative Szemerédi theorem
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Largest subgraph from a hereditary property in a random graph
• Random sum-free subsets of abelian groups
• Online containers for hypergraphs, with applications to linear equations
• Relative Turán problems for uniform hypergraphs
• Hypergraph containers
• The Maker-Breaker Rado game on a random set of integers
• Extremal results for odd cycles in sparse pseudorandom graphs
• Hypergraph removal lemmas via robust sharp threshold theorems
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• Dirac-type theorems in random hypergraphs
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• A density version of the Carlson-Simpson theorem
• Maximum-size antichains in random set-systems
• An analogue of the Erdős-Gallai theorem for random graphs
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• The power of many colours
• A note on sparse supersaturation and extremal results for linear homogeneous systems
• Weakly saturated random graphs
• scientific article; zbMATH DE number 1471868 (Why is no real title available?)
• Independent sets in algebraic hypergraphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Four‐term progression free sets with three‐term progressions in all large subsets
• An asymmetric random Rado theorem: 1-statement
• On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
• Turán theorems for even cycles in random hypergraph
• Triangle-free subgraphs of hypergraphs
• Pancyclic subgraphs of random graphs
• Random polynomial graphs for random Turán problems
• The regularity method for graphs with few 4‐cycles
• Extremal Sidon sets are Fourier uniform, with applications to partition regularity
• Highly sparse sets as additive complements for a prescribed density
• Normal limiting distributions for systems of linear equations in random sets
• Lower tails via relative entropy
• Combinatorics of NC-probability spaces with independent constants
• Upper bounds for the number of substructures in finite geometries from the container method
• An efficient container lemma
• An analytic approach to sparse hypergraphs: hypergraph removal
• Probabilistic hypergraph containers
• Highly spare sets as additive complements for a prescribed density: an open problem
• Counting configuration-free sets in groups
• On \(k\)-uniform random hypergraphs without generalized fans
• A short nonalgorithmic proof of the containers theorem for hypergraphs
• A randomized version of Ramsey's theorem

This page was built for publication: Combinatorial theorems in sparse random sets

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