Extremal results in random graphs

Vojtěch Rödl, Mathias Schacht

Published 2013-02-09, updated 2013-04-03Version 2

According to Paul Erd\H{o}s [Some notes on Tur\'an's mathematical work, J. Approx. Theory 29 (1980), page 4] it was Paul Tur\'an who "created the area of extremal problems in graph theory". However, without a doubt, Paul Erd\H{o}s popularized extremal combinatorics, by his many contributions to the field, his numerous questions and conjectures, and his influence on discrete mathematicians in Hungary and all over the world. In fact, most of the early contributions in this field can be traced back to Paul Erd\H{o}s, Paul Tur\'an, as well as their collaborators and students. Paul Erd\H{o}s also established the probabilistic method in discrete mathematics, and in collaboration with Alfr\'ed R\'enyi, he started the systematic study of random graphs. We shall survey recent developments at the interface of extremal combinatorics and random graph theory.