Journal article icon

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

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

Actions


Access Document


Files:
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:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP