Large deviations in random graphs

Abstract

What is the probability that the number of triangles in an Erd\H{o}s–R\'enyi random graph exceeds its mean by a constant factor?

This problem has been a useful litmus test for concentration bound techniques. Even the order of the log-probability was considered a difficult problem until its resolution a few years ago by Chatterjee and DeMarco--Kahn. I will discuss the problem of determining the exponential rate of the tail probability, and survey some recent developments and open problems.