Large deviation principle for graphons

Abstract: In this talk we discuss the large deviation principle (LDP) for a sequence of measures on the graphon space which is obtained by sampling from a fixed graphon W.

The large deviation theory for the Erdős–Rényi random graph (sampling from a constant graphon) and its applications were developed by Chatterjee and Varadhan.

Particularly, the Erdős–Rényi random graph satisfies LDP with the speed $2/n^2$.

We show that when sampling from a general graphon one can get LDPs with two interesting speeds, namely, $1/n$ and $2/n^2$. We completely characterize the situation for the speed $1/n$. In the case $2/n^2$, we describe the LDP when sampling from a step graphon.

Time permitting, we compare our work with a recent result by Borgs, Chayes, Gaudio, Petti and Sen on LDP for block models.

This is a joint work with O.Pikhurko.

combinatoricsprobability

Audience: researchers in the topic

---

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).

---