Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2016 | Submitted + Published
Journal Article Open

Combinatorial theorems in sparse random sets

Abstract

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.

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.

Attached Files

Published - 44072019.pdf

Submitted - 1011.4310.pdf

Files

1011.4310.pdf
Files (2.7 MB)
Name Size Download all
md5:71fbf27970281745fd83fa928e3c4d6b
606.4 kB Preview Download
md5:0160b9a8d6ee84550424c70dbc57fa20
2.1 MB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 18, 2023