Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, February 21, 2017 - 3:00pm

Shirshendu Ganguly

Berkeley

Location

University of Pennsylvania

DRL 3C8

 
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.