Some large deviation results for sparse random graphs
By: Neil O'Connell.
Contributors: Hewlett-Packard Laboratories.
Series: [Technical report] / HP Laboratories Bristol. Basic Research Institute in the Mathematical Sciences -- HPL-BRIMS-96-22.; BRIMS technical report -- HPL-BRIMS-96-22.
Publisher: Hewlett Packard
Published: 1996
Place of publication: Bristol [England]
Language: eng
Number of pages: 15
Subjects: Large deviations; Graph theory; Random graphs
Description: 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 an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, wheich 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.)."
Notes: Cover title.

"September, 1996."

Includes bibliographical references.