In the exponential random graph model, one samples an n-vertex random graph G with probability proportional to exp(f(G)), where f(G) is some graph parameter.
The large deviation problem asks for the asymptotics of the log-probaiblity of the rare event that, for a binomial random graph G, some graph parameter f(G) (such as the number of triangles in G) exceeds its expectation, say, by a constant factor.
These two problems are intimately related to each other, and both are quite difficult in general to analyze rigorously. Many problems are open, for instance, the structure of a "typical" instance of an exponential random graph is not known in most cases (though we have solutions in some special cases). I will survey some recent progress, in particular highlighting recent works of Chatterjee, Varadhan, Diaconis, Dembo, and Eldan on the development of new techniques for estimating the partition function of an exponential random graph model and its applications to large deviations estimation.
more upcoming events
No upcoming events