HP Labs Technical Reports

Some Large Deviation Results for Sparce Random Graphs

O'Connell, Neil

HPL-BRIMS-96-22

Keyword(s): giant component; connectivity; isolated vertices

Abstract: We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. As a corollary we present an asymptotic formula for the probability that the random graph is connected. We also present a LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling the properties 'connected' and 'contains no isolated vertices' are not asymptotically equivalent. ( At the threshold probability they are asymptotically equivalent.)

Back to Index