Random Regular Graphs: Asymptotic Distributions and Contiguity

Combinatorics Probability and Computing - Tập 4 Số 4 - Trang 369-405 - 1995
Svante Janson1
1 Uppsala University

Tóm tắt

The asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose logarithm can be written as an infinite linear combination of independent Poisson variables, and thus the logarithm has an infinitely divisible distribution with a certain discrete Lévy measure. Similar results are found for some related problems. These limit results imply that some different models of random regular graphs are contiguous, which means that they are qualitatively asymptotically equivalent. For example, if r > 3, then the usual (uniformly distributed) random r-regular graph is contiguous to the one constructed by taking the union of r perfect matchings on the same vertex set (assumed to be of even cardinality), conditioned on there being no multiple edges. Some consequences of contiguity for asymptotic distributions are discussed.

Từ khóa


Tài liệu tham khảo

10.1016/S0095-8956(81)80022-6

[17] Molloy M. , Robalewska-Szarłat H. , Robinson R.W. and Wormald N.C. (to appear) 1-factorisations of random regular graphs.

[18] Robalewska-Szarłat H. (to appear) 2-factors in random regular graphs.

10.1016/0095-8956(86)90029-8

10.1007/978-1-4612-4946-7

10.1002/rsa.3240050209

10.1002/rsa.3240010403

Skorokhod, 1956, Limit theorems for stochastic processes, Teor. Veroyatnost. i Primenen, 1, 289

Bollobás, 1985, Random Graphs

Billingsley, 1968, Convergence of Probability Measures.

10.1002/rsa.3240030202

10.1017/CBO9780511804373

Le Cam, 1960, Locally asymptotically normal families of distributions, Univ. of California Publ. in Statistics, 3, 37

Robinson, 1984, Enumeration and Design, 251

10.1016/0097-3165(78)90059-6

Janson, 1994, Orthogonal decompositions and functional limit theorems for random graph statistics. Memoirs Amer. Math. Soc., 534

10.1016/S0195-6698(80)80030-8

10.1002/rsa.3240030303

Loève, 1977, Probability theory

10.1017/S096354830000095X

[14] Le Cam L. (1969) Théorie asymptotique de la décision statistique. Les Presses de l'université de Montréal.

Cooper, Perfect matchings in random r-regular, s-uniform hypergraphs, Combinatorics, Probability and Computing

10.1017/S0963548300001012

Frieze, Generating and counting Hamilton cycles in random regular graphs, Journal of Algorithms

Thông tin
Thông tin xuất bản

Combinatorics Probability and Computing

Tập 4 Số 4

369-405

Thông tin tác giả