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 independently by Conlon and Gowers.
Full Article