Asymptotic normality in random graphs with given vertex degrees.

12 February 2019
Svante Janson

We study random (simple) graphs with given vertex degrees, in the sparse case where the average degree is bounded. Assume also that the second moment of the vertex degree is bounded. The standard method then is to use the configuration model to construct a random multigraph and condition it on
being simple.

This works well for results of the type that something holds with high probability, or that something converges in probability, but it does not immediately apply to convergence in distribution, for example asymptotic normality. (Although this has been done by special arguments in a couple of cases, by Janson and Luczak and by Riordan.) A typical example is the recent result by Barbour and Röllin on asymptotic normality of the size of the giant component of the multigraph (in the supercritical case); it is an obvious conjecture that the same results hold for the random simple graph.

We discuss two new approaches to this, both based on old methods. Both apply to the size of the giant component, using rather minor special arguments.

One approach uses the method of moments to obtain joint convergence of the variable of interest together with the numbers of loops and multiple edges
in the  multigraph.

The other approach uses switchings to modify the multigraph and construct a simple graph. This simple random graph will not have a uniform distribution,
but almost, and this is good enough.

  • Combinatorial Theory Seminar