Extremal results for random discrete structures
arXiv:1603.00894 · doi:10.4007/annals.2016.184.2.1
Abstract
We study thresholds for extremal properties of random discrete structures. We determine the threshold for Szemerédi's theorem on arithmetic progressions in random subsets of the integers and its multidimensional extensions and we determine the threshold for Turán-type problems for random graphs and hypergraphs. In particular, we verify a conjecture of Kohayakawa, Łuczak, and Rödl for Turán-type problems in random graphs. Similar results were obtained by Conlon and Gowers.
32 pages
Cited by in corpus (9)
- Upper tails for arithmetic progressions in random subsets
- On the missing log in upper tail estimates
- Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
- Weakly saturated random graphs
- On the number of H-free hypergraphs
- On zero-sum free sequences contained in random subsets of finite cyclic groups
- Normal limiting distributions for systems of linear equations in random sets
- The power of many colours
- Maximum chordal subgraphs of random graphs