Sub-critical exponential random graphs: concentration of measure and some applications (Q6567137)

The main goal of this paper is to study the properties of Glauber dynamics, the concentration of measure, and the central limit theorem for the number of edges in exponential random graph models in the high-temperature (subcritical regime). The definition of these random graphs starts with a fixed family of finite graphs \(G_1, G_2, \ldots, G_s\). For each graph \(H\) on \(n\) vertices, we can count the number of copies of \(G_i\) in \(H\), and the probability that we choose \(H\) depends on these subgraph counts; more precisely, the Hamiltonian is a weighted sum of these homomorphism densities. Earlier studies show that exponential random graphs asymptotically behave similarly to Erdős-Rényi random graphs from certain points of view, and it had already been known that Glauber dynamics is rapidly mixing in the high-temperature regime on exponential random graphs, that is when there are unique maximizers of the partition function. The current paper studies the asymptotic behavior of this family in more detail in this setup.\N\NMore precisely, first, the authors give a sharp upper bound on the relaxation time in the high-temperature regime. Then they prove that Lipschitz functions mapping from the family of graphs on \(n\) vertices are strongly concentrated if they are evaluated at an exponential random graph. Using this, it is proved that a central limit theorem is satisfied for the normalized number of open edges within a growing family of pairs of vertices. This strengthens the already known statements on the connections of exponential random graphs in the high-temperature regime and Erdős-Rényi random graph (where all edges are independent, so the central limit theorem always holds). Going further, the paper provides a quantitative version of the similarity of the two models by giving an upper bound of order \(n^{3/2}\sqrt{\log n}\) on the Wasserstein distance of the distribution of the exponential random graph and the Erdős-Rényi random graph on \(n\) vertices, with edge probabilities chosen appropriately.\N\NThe proofs are based on various methods from statistical physics and probability theory, including Dobrushin's condition for the uniqueness of Gibbs measure, Poincaré inequality, Stein's method for concentration of exchangeable random variables, and FKG inequality guaranteeing the non-negativity of pairwise correlations of random variables corresponding to different edges.