turkmath.org

We will consider some of the classic results in probabilistic graph theory and see why they are of interest to others working in the field. We will then consider some contemporary applications. In particular, we will show that if H is a fixed graph and G is a graph drawn at random from the set of all graphs on n vertices, then it is almost surely the case that every set with at least log(n) vertices in G contains an induced copy of H. Here, the base of the log depends on G. This provides extremal graphs in many different situations.