Large deviations in randomly coloured random graphs

by J.D.Biggins and D.B. Penman

2000 Mathematics Subject Classification: Primary 60F10; secondary 05C80


Models of random graphs where the presence or absence of an edge depends on the random types (colours) of its vertices, so that whether or not edges are present can be dependent, are considered. In particular, large deviations in the number of edges are studied. An application of a result on large deviations for mixtures allows a fairly complete treatment of this question. This is a natural example with two different non-degenerate large deviation regimes, one arising from large deviations in the colourings followed by typical edge placement and the other from large deviation in edge placement.


Preprint 537/03, Department of Probability and Statistics, University of Sheffield. (September 2003). pdf file or ps file

Electronic Communications in Probability (2009) 14, 290-301

Other publications by J.D. Biggins

Return to my home page