thresholds for monotone graph properties

A graph property is monotone increasing if adding edges can never destroy it: connectivity, containing a triangle, containing a perfect matching, being Hamiltonian are all increasing, while their negations are monotone decreasing. The central discovery of random graph theory is that essentially every monotone property has a threshold: a function p*(n) such that if p is much smaller than p* the property holds with probability tending to 0, and if p is much larger it holds with probability tending to 1. The question this answers is: at what edge density does a desired feature suddenly appear?

The precise statement, due to Bollobas and Thomason, is that every nontrivial monotone property has a threshold function p*(n), meaning there exists p*(n) so that P(G(n,p) has the property) tends to 0 when p/p* tends to 0 and tends to 1 when p/p* tends to infinity. The threshold is determined only up to constants by this definition (it is a coarse threshold in general). The intuitive reason it exists at all is monotonicity plus a coupling argument: one can build G(n,p) and G(n,q) for p < q on the same probability space so that the first is a subgraph of the second, which forces the probability of an increasing property to be a nondecreasing, in fact rather steeply rising, function of p. Different properties have wildly different thresholds: the appearance of a fixed subgraph H with 'densest part' having edge-to-vertex ratio rho has threshold p* = n^(-1/rho); connectivity has threshold (log n)/n; a triangle appears at p* = 1/n.

Thresholds are the organizing principle of the whole subject — almost every result is a threshold statement. They matter because they convert vague questions ('when does the graph become connected?') into sharp quantitative laws, and because the methods used to locate them (first and second moment methods, the branching heuristic, coupling) are reusable across combinatorics, statistical physics and theoretical computer science. A caveat worth stating: 'has a threshold' is a weaker statement than 'has a sharp threshold'. The Bollobas-Thomason theorem guarantees a threshold up to a constant factor for every monotone property, but whether the transition is sharp (happens in a window much narrower than the threshold itself) is a separate and often deep question, settled in general by the Friedgut-Kalai and Friedgut sharp-threshold theory.