Journal article

### 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...

Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

### Access Document

Files:
• (pdf, 605.6KB)
Publisher copy:
10.4007/annals.2016.184.2.2

### Authors

More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Role:
Author
Publisher:
Princeton University, Department of Mathematics Publisher's website
Journal:
Annals of Mathematics Journal website
Volume:
184
Pages:
367-454
Publication date:
2016-07-29
Acceptance date:
2016-04-07
DOI:
EISSN:
1939-8980
ISSN:
0003-486X
URN:
uuid:f8323c69-44af-4aec-abc3-84e3e239af4f
Source identifiers:
196714
Local pid:
pubs:196714
Paper number:
2
Keywords: