Large deviations in randomly coloured random graphs

J. D. Biggins (The University of Sheffield, UK)
D.B. Penman (University of Essex, UK)

Abstract


Models of random graphs are considered 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. The principal objective is to study large deviations in the number of edges. These graphs provide 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. A secondary objective is to illustrate the use of a general result on large deviations for mixtures.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 290-301

Publication Date: July 10, 2009

DOI: 10.1214/ECP.v14-1478

References

  1. Biggins, J.D. Large deviations for mixtures. Electron. Comm. Probab., 9 (2004), 60-71. (electronic). MR2081460 (2005k:60082)
  2. Bollob·s, BÈla. Random graphs. (1985). Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London. MR0809996 (87f:05152)
  3. Bollob·s, BÈla; Janson, Svante; Riordan, Oliver. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 (2007), 3-122. MR2337396 (2008e:05124)
  4. Cannings, C; Penman, D.B. Models of random graphs and their applications. Stochastic processes: modelling and simulation, Handbook of Statist., 21, (2003), 51-91. North-Holland, Amsterdam MR1973541 (2004c:05181)
  5. Cerquetti, Annalisa; Fortini, Sandra. A Poisson approximation for coloured graphs under exchangeability. Sankhya 68 (2006), 183-197. MR2303080 (2007m:60056)
  6. Chaganty, Narasinga R. Large deviations for joint distributions and statistical applications. Sankhya Ser. A 59 (1997), 147-166. MR1665683 (2000b:60067)
  7. Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Jones and Bartlett Publishers, Boston, MA, (1993) MR1202429 (95a:60034)
  8. Dinwoodie, I. H.; Zabell, S. L. Large deviations for exchangeable random vectors. Ann. Probab. 20 (1992), 1147-1166. MR1175254 (93g:60059)
  9. Doku-Amponsah, Kwabena; Mörters, Peter. Large deviation principles for empirical measures of coloured random graphs. arXiv:math/0607545v1 (2006).
  10. Penman. D.B. Random graphs with correlation structure. Ph.D thesis, University of Sheffield, (1998).
  11. Rockafellar, R. Tyrrell. Convex analysis. Princeton Mathematical Series, 28. Princeton University Press, Princeton, N.J. (1970) MR0274683 (43 #445)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.