Simon Griffith: Moderate deviation probabilities for subgraphs and other discrete structures

Tid: On 2019-01-16 kl 15.15 - 16.15

Föreläsare: Simon Griffith

Plats: Room 306, House 6, Kräftriket, Department of Mathematics, Stockholm University 

Abstract: We may trace the origins of the theory of large deviations, which considers the probability that a random variable takes a value far from its mean, to the work of Swedish mathematician Harald Cramér in the 1930s. The general theory was further developed by Varadhan from the 1960s onwards. In recent decades, many articles have focused on deviation probabilities for subgraph counts in the Erd\H{o}s-R\'enyi random graph \(G(n,p)\).

In this talk we consider the probability of moderately large deviations of subgraph counts in the alternative random graph model \(G(n,m)\) (also named after Erd\H{o}s and R\'enyi), in which the number of edges is fixed. We present the asymptotic rate associated with such deviations and deduce related bounds for the \(G(n,p)\) model.

Finally, we mention recent work in which we apply similar methods in a more general discrete framework.

[Based on join work with Christina Goldschmidt and Alex Scott, and Gonzalo Fiz Pontiveros, Matheus Secco and Oriel Serra.]