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

### Access Document

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

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
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
Source identifiers:
196714
Keywords:
Pubs id:
pubs:196714
UUID:
uuid:f8323c69-44af-4aec-abc3-84e3e239af4f
Local pid:
pubs:196714
Deposit date:
2016-04-29