Abstract

The Erdös—Rényi or `binomial’ random graph G(n,p) consists of n vertices, with each pair connected by an edge with probability p, independently of the others. The nature of the model means that `local’ properties (such as individual vertex degrees) tend to be relatively easy to study, whereas `global’ properties (such as the size of the largest component) are much harder. An interesting class of questions relates one to the other. For example, if p=p(n) is chosen so that G(n,p) has whp (`with high probability’, i.e., with probability tending to 1 as n tends to infinity) minimum degree at least 1, does it also have (whp) the global property of connectedness? The answer is yes, as shown already by Erdös and Rényi in 1960. What about minimum degree 2 and containing a Hamilton cycle? Again yes, as shown by Komlós and Szemerédi in 1983. What about every vertex being in a triangle, and the graph containing a triangle factor, i.e., a set of n/3 disjoint triangles covering all the vertices? This question turned out to be much harder, and was eventually answered (approximately) by Johansson, Kahn and Vu in 2008.

In this talk I will describe at least some aspects of the proof of the last result, as well as a related recent development. The aim is not so much to present particular results, but rather to give a flavour of the range of methods that are used in studying this type of problem.