The upper tail problem in the Erd ?os-R �enyi random graph G ~ Gn,p, where every edge is included independently with probability p, is to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1 + d. The arithmetic analog considers the count of arithmetic progressions in a random subset of Z/nZ, where every element is included independently with probability p. In this talk, I will describe some recent results regarding the solution of the upper tail problem in the sparse setting i.e. where p decays to zero, as n grows to infinity. The solution relies on non-linear large deviation principles developed by Chatterjee and Dembo and more recently by Eldan and solutions to various extremal problems in additive combinatorics.
Probability and Combinatorics
Tuesday, February 21, 2017 - 3:00pm
Shirshendu Ganguly
Berkeley