Extremal results for random discrete structures

• 成果类型: Article
• 署名作者: Schacht, Mathias
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2016.184.2.1
• 发表日期: 2016
• 页码: 333-365
• 关键词: Random graphs; ramsey properties; random subsets; subgraphs; THEOREM

摘要

We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemeredi's theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions, and we determine the threshold for Turan-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, Luczak, and Rodl for Turan-type problems in random graphs. Similar results were obtained independently by Conlon and Gowers.