Mathematics Colloquium

Suppose that Y_1, ..., Y_N are i.i.d. (independent identically distributed) random variables and let X = Y_1 + ... + Y_N. The classical theory of large deviations allows one to accurately estimate the probability of the tail events X < (1-c)E[X] and X > (1+c)E[X] for any positive c. However, the methods involved strongly rely on the fact that X is a linear function of the independent variables Y_1, ..., Y_N. There has been considerable interest—both theoretical and practical—in developing tools for estimating such tail probabilities also when X is a nonlinear function of the Y_i. One archetypal example studied by both the combinatorics and the probability communities is when X is the number of copies of a given graph H in the binomial random graph G(n,p). I will discuss recent developments in the study of the tail probabilities of this random variable. The talk is based on joint works with Asaf Cohen-Antonir, Matan Harel, and Frank Mousset and with Gady Kozma.