Combinatorial theorems in sparse random sets

DOI10.4007/annals.2016.184.2.2zbMath1351.05204arXiv1011.4310OpenAlexW2964207251WikidataQ97694159 ScholiaQ97694159MaRDI QIDQ350550

David Conlon, 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

zbMATH Keywords

random graphs extremal combinatorics random sets sparse analogues

Mathematics Subject Classification ID

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

Related Items (92)

Independent sets in algebraic hypergraphs ⋮ Polynomial configurations in subsets of random and pseudo-random sets ⋮ Dirac-type theorems in random hypergraphs ⋮ The number of $C_{2\ell}$-free graphs ⋮ Arcs in $\mathbb{F}_q^2$ ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Pancyclic subgraphs of random graphs ⋮ Online containers for hypergraphs, with applications to linear equations ⋮ Normal limiting distributions for systems of linear equations in random sets ⋮ A new proof of the KŁR conjecture ⋮ Extremal results for random discrete structures ⋮ A note on sparse supersaturation and extremal results for linear homogeneous systems ⋮ Triangle resilience of the square of a Hamilton cycle in random graphs ⋮ Supersaturation in posets and applications involving the container method ⋮ On the stability of the Erdős-Ko-Rado theorem ⋮ A probabilistic threshold for monochromatic arithmetic progressions ⋮ Rectilinear approximation and volume estimates for hereditary bodies via [0, 1‐decorated containers] ⋮ On an anti-Ramsey threshold for random graphs ⋮ An asymmetric random Rado theorem for single equations: The 0‐statement ⋮ Four‐term progression free sets with three‐term progressions in all large subsets ⋮ Covering random graphs with monochromatic trees ⋮ Ramsey goodness of trees in random graphs ⋮ Seymour's second neighborhood conjecture for orientations of (pseudo)random graphs ⋮ Largest subgraph from a hereditary property in a random graph ⋮ Lower tails via relative entropy ⋮ SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS ⋮ Solutions to certain linear equations in Piatetski-Shapiro sequences ⋮ On the maximum $F_5$-free subhypergraphs of a random hypergraph ⋮ Random polynomial graphs for random Turán problems ⋮ Extremal Sidon sets are Fourier uniform, with applications to partition regularity ⋮ Turán‐type problems for long cycles in random and pseudo‐random graphs ⋮ On zero-sum free sequences contained in random subsets of finite cyclic groups ⋮ Infinite Sidon Sets Contained in Sparse Random Sets of Integers ⋮ The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups ⋮ A Short Proof of the Random Ramsey Theorem ⋮ On the Number ofB_h-Sets ⋮ Partition regularity and the primes ⋮ Simple Containers for Simple Hypergraphs ⋮ Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability ⋮ Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers ⋮ Counting configuration-free sets in groups ⋮ Extremal results in sparse pseudorandom graphs ⋮ A short nonalgorithmic proof of the containers theorem for hypergraphs ⋮ The number of $K_{m,m}$-free graphs ⋮ On the cycle space of a random graph ⋮ On the KŁR conjecture in random graphs ⋮ An analogue of the Erdős-Gallai theorem for random graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ A density version of the Carlson-Simpson theorem ⋮ Extremal results for odd cycles in sparse pseudorandom graphs ⋮ On the number of monotone sequences ⋮ Hypergraph containers ⋮ The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture ⋮ An analytic approach to sparse hypergraphs: hypergraph removal ⋮ Spatially independent martingales, intersections, and applications ⋮ Relative Turán Problems for Uniform Hypergraphs ⋮ The Maker--Breaker Rado Game on a Random Set of Integers ⋮ On $k$-uniform random hypergraphs without generalized fans ⋮ An algorithmic framework for obtaining lower bounds for random Ramsey problems ⋮ An exponential-type upper bound for Folkman numbers ⋮ Counting configuration-free sets in groups ⋮ Random differences in Szemerédi's theorem and related results ⋮ Stability results for random discrete structures ⋮ On two-point configurations in subsets of pseudo-random sets ⋮ Mantel's theorem for random hypergraphs ⋮ The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers ⋮ Unnamed Item ⋮ Counting sum-free sets in abelian groups ⋮ Random sum-free subsets of abelian groups ⋮ The typical structure of sparse $K_{r+1}$-free graphs ⋮ Bivariate fluctuations for the number of arithmetic progressions in random sets ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ Many $T$ copies in $H$-free graphs ⋮ Covering graphs by monochromatic trees and Helly-type results for hypergraphs ⋮ Roth's theorem in the Piatetski-Shapiro primes ⋮ On Erdős–Ko–Rado for Random Hypergraphs II ⋮ An efficient container lemma ⋮ Triangle-free subgraphs of hypergraphs ⋮ Ramsey games near the critical threshold ⋮ Maximum-size antichains in random set-systems ⋮ On Erdős–Ko–Rado for random hypergraphs I ⋮ A sharp threshold for van der Waerden's theorem in random subsets ⋮ Bandwidth theorem for random graphs ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Ramsey properties of randomly perturbed graphs: cliques and cycles ⋮ Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers ⋮ An asymmetric random Rado theorem: 1-statement ⋮ Independent sets in hypergraphs ⋮ Counting independent sets in graphs ⋮ A multi-dimensional Szemerédi theorem for the primes via a correspondence principle ⋮ The regularity method for graphs with few 4‐cycles ⋮ A relative Szemerédi theorem

Cites Work

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