Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T02:18:19.649Z Has data issue: false hasContentIssue false
  • English
  • Français

General percolation and random graphs

Published online by Cambridge University Press:  01 July 2016

Colin McDiarmid
Colin McDiarmid*
Affiliation:
University of Oxford
*
∗Postal address: Wolfson College, Oxford OX2 6UD, U.K.
Get access Rights & Permissions [Opens in a new window]

Abstract

I introduce some useful general results concerning clutter percolation and families of binary random variables arranged in independent subfamilies, and give several applications to the study of random graphs and digraphs.

Keywords

DEPENDENT RANDOM VARIABLESHAMILTONIAN GRAPHSCLUTTERRELIABILITY
Type
Research Article
Information
Advances in Applied Probability , Volume 13 , Issue 1 , March 1981 , pp. 40 - 60
Copyright
Copyright © Applied Probability Trust 1981 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This research was supported in part by Canadian NRC grant A9211.

References

[1] Angluin, D. and Valiant, L. G. (1977) Fast probabilistic algorithms for Hamiltonian circuits and matchings. Internal Report CSR-17-77 , University of Edinburgh.CrossRefGoogle Scholar
[2] Barlow, R. E. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing. Holt, Rinehart, and Winston, New York.Google Scholar
[3] Birnbaum, Z. W., Esary, J. D. and Saunders, S. C. (1961) Multicomponent systems and structures and their reliability. Technometrics 3, 55–77.CrossRefGoogle Scholar
[4] Bondy, J. A. (1978) Hamiltonian cycles in graphs and digraphs. Research Report CORR 78–16, University of Waterloo.Google Scholar
[5] Bondy, J. A. and Murty, U.S.R. (1977) Graph Theory with Applications. Macmillan, London.Google Scholar
[6] Butterworth, R. W. (1972) A set theoretic treatment of coherent systems. SIAM J. Appl. Math. 4, 590–598.CrossRefGoogle Scholar
[7] Chvátal, V. and Thomassen, C. (1978) Distances in orientations of graphs, J. Combinatorial Theory B 24, 61–75.CrossRefGoogle Scholar
[8] Edmonds, J. and Fulkerson, D. R. (1970) Bottleneck extrema. J. Combinatorial Theory 8, 299–306.CrossRefGoogle Scholar
[9] Esary, J. D. and Proschan, F. (1963) Coherent structures of non-identical components. Technometrics 5, 191–201.CrossRefGoogle Scholar
[10] Frank, H. and Frisch, I. T. (1971) Communication, Transmission and Transportation Networks. Addison-Wesley, New York.Google Scholar
[11] Frisch, H. L. and Hammersley, J. M. (1963) Percolation processes and related topics. J. SIAM 11, 894–918.Google Scholar
[12] Hammersley, J. M. (1961) Comparison of atom and bond percolation processs. J. Math. Phys. 2, 728–733.CrossRefGoogle Scholar
[13] Hammersley, J. M. and Walters, R. S. (1963) Percolation and fractional branching processes. J. SIAM 11, 831–839.Google Scholar
[14] Komlós, J. and Szemerédi, E. (1980) Limit distribution for the existence of Hamiltonian cycles in a random graph.Google Scholar
[15] McDiarmid, C. J. H. (1980) Clutter percolation and random graphs. Math. Progr. Study 13, 17–25.CrossRefGoogle Scholar
[16] McDiarmid, C. J. H. (1980) General first-passage percolation. To appear.Google Scholar
[17] Nash-Williams, C. St. J. A. (1960) On orientations, connectivity and odd-vertex pairings in finite graphs. Canad. J. Math. 12, 555–567.CrossRefGoogle Scholar
[18] Oxley, J. G. and Welsh, D. J. A. (1979) On some percolation results of J. M. Hammersley, J. Appl. Prob. 16, 526–540.CrossRefGoogle Scholar
[19] Satyanarayana, A. and Prabhakar, A. (1978) New topological formula and rapid algorithm for reliability analysis of complex networks. IEEE Trans. Reliability R-27, 82–100.CrossRefGoogle Scholar
[20] Seymour, P. D. (1976) The forbidden minors of binary clutters. J. London Math. Soc. (2) 12, 356–360.CrossRefGoogle Scholar
[21] Walkup, D. W. (1976) Pólya sequences, binomial convolution and the union of random sets. J. Appl. Prob. 13, 76–85.CrossRefGoogle Scholar