HP Labs Technical Reports
Click here for full text:
Some Large Deviation Results for Sparce Random Graphs
O'Connell, Neil
HPLBRIMS9622
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
