A Caltech Library Service

Combinatorial theorems in sparse random sets

Conlon, D. and Gowers, W. T. (2016) Combinatorial theorems in sparse random sets. Annals of Mathematics, 184 (2). pp. 367-454. ISSN 0003-486X. doi:10.4007/annals.2016.184.2.2.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Turán’s theorem, Szemerédi’s theorem and Ramsey’s theorem, hold almost surely inside sparse random sets. For instance, we extend Turán’s theorem to the random setting by showing that for every ϵ > 0 and every positive integer t ≥ 3 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 Cn^(−2/(t+1)), then, with probability tending to 1 as n tends to infinity, every subgraph of G with at least (1 – (1/(t−1)) + ϵ)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án 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ödl and Schacht.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, D.0000-0001-5899-1829
Additional Information:© 2016 D. Conlon and W.T. Gowers; this is the published version of arXiv 1011.4310. Received 18 November 2010; revised 2 February 2015; accepted 7 April 2016; published online 29 July 2016. Research of D.C. supported by a Royal Society University Research Fellowship. Research of W.T.G. supported by a Royal Society 2010 Anniversary Research Professorship.
Funding AgencyGrant Number
Subject Keywords:Extremal combinatorics, random graphs and sets, sparse analogues
Issue or Number:2
Classification Code:Primary: 05C35, 05C80, 11B30
Record Number:CaltechAUTHORS:20190812-162957976
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97813
Deposited By: Melissa Ray
Deposited On:15 Aug 2019 17:43
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page