Random regular graphs: Asymptotic distributions and contiguity. (English) Zbl 0846.05076
This paper extends the important work of Robinson and Wormald by deriving the asymptotic distribution of the number of hamiltonian cycles in a random regular graph. The paper also describes some generalizations as well as extensions to some related problems. Of particular interest is the idea of contiguity by Le Cam, but used for the first time, I think, in random graphs in this paper. Contiguity is an equivalence relation among sequences of probability measures. Its usefulness in this paper is that it allows one to establish the asymptotic distribution of the number of hamiltonian cycles, say, for different models of random regular graphs. All that is needed is to establish the equivalence of the new model to the studied model via contiguity.
Reviewer: R.Vohra (Columbus/Ohio)
Keywords:
asymptotic distribution; hamiltonian cycles; random regular graph; continuity; probability measuresReferences:
| [1] | Roussas, Contiguity of probability measures: some applications in statistics (1972) · Zbl 0265.60003 · doi:10.1017/CBO9780511804373 |
| [2] | Skorokhod, Teor. Veroyatnost. i Primenen 1 pp 289– (1956) |
| [3] | DOI: 10.1002/rsa.3240030202 · Zbl 0755.05075 · doi:10.1002/rsa.3240030202 |
| [4] | Frieze, Journal of Algorithms |
| [5] | Cooper, Combinatorics, Probability and Computing |
| [6] | DOI: 10.1017/S096354830000095X · Zbl 0809.05081 · doi:10.1017/S096354830000095X |
| [7] | DOI: 10.1016/0095-8956(86)90029-8 · Zbl 0602.05050 · doi:10.1016/0095-8956(86)90029-8 |
| [8] | Bollobás, Random Graphs (1985) |
| [9] | Bollobás, Europ. J. Combinatorics 1 pp 311– (1980) · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8 |
| [10] | Billingsley, Convergence of Probability Measures. (1968) · Zbl 0172.21201 |
| [11] | DOI: 10.1016/0097-3165(78)90059-6 · Zbl 0402.05042 · doi:10.1016/0097-3165(78)90059-6 |
| [12] | DOI: 10.1002/rsa.3240010403 · Zbl 0733.05050 · doi:10.1002/rsa.3240010403 |
| [13] | Robinson, Enumeration and Design pp 251– (1984) |
| [14] | Loève, Probability theory (1977) · doi:10.1007/978-1-4684-9464-8 |
| [15] | Le Cam, Asymptotic methods in statistical decision theory (1986) · Zbl 0605.62002 · doi:10.1007/978-1-4612-4946-7 |
| [16] | Le Cam, Univ. of California Publ. in Statistics 3 pp 37– (1960) |
| [17] | DOI: 10.1017/S0963548300001012 · Zbl 0809.05084 · doi:10.1017/S0963548300001012 |
| [18] | Janson, Orthogonal decompositions and functional limit theorems for random graph statistics. Memoirs Amer. Math. Soc. 534 (1994) · Zbl 0810.05001 |
| [19] | DOI: 10.1002/rsa.3240030303 · Zbl 0771.05089 · doi:10.1002/rsa.3240030303 |
| [20] | DOI: 10.1016/S0095-8956(81)80022-6 · Zbl 0442.05042 · doi:10.1016/S0095-8956(81)80022-6 |
| [21] | DOI: 10.1002/rsa.3240050209 · Zbl 0795.05088 · doi:10.1002/rsa.3240050209 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
