Exponential approximation,method of types for empirical neighbourhood distributions for random graphs by random allocation

Abstract

In this article we find exponential good approximation of the empirical neigbourhood distribution ofsymbolled random graphs conditioned to a given empirical symbol distribution and empirical pair distribution.Using this approximation we shorten or simplify the proof of (Doku-Amponsah and Morters 2010, Theorem 2.5);the large deviation principle (LDP) for empirical neigbourhood distribution of symbolled random graphs. We alsoshow that the LDP for the empirical degree measure of the classical Erd˝os-R´enyi graph is a special case of (Doku-Amponsah and Moerters, 2010, Theorem 2.5). From the LDP for the empirical degree measure, we derive an LDP for the the proportion of isolated vertices in the classical Erd˝os-R´enyi graph.