Sparse random graphs with unusually large subgraph counts

In this talk, based on joint works with Nicholas Cook, Huy Tuan Pham and Sohom Bhattacharya, I will discuss recent developments in the emerging theory of nonlinear large deviations, focusing on sharp upper tails for counts of several fixed subgraphs in a large sparse random graph (such as Erdős–Rényi or uniformly d-regular). These results allow in turn to determine the typical structure of samples from an associated class of Gibbs measures, known as Exponential Random Graph Models, which are widely used in the analysis of social networks.
 
(14:00-15:00 UTC)  Speaker: Nicholas Cook

Large deviations and the regularity method for the Erdős–Rényi (hyper)graph

I will describe a quantitative approach to the large deviations of random graphs and hypergraphs, emphasizing connections with graph limit theory and the regularity method from extremal combinatorics. The approach rests on new decomposition theorems and counting lemmas for sparse hypergraphs, formulated in terms of a novel class of cut-type norms for Bernoulli tensors. Based on joint work with Amir Dembo and Huy Tuan Pham.