RANDOM REGULAR GRAPHS: ASYMPTOTIC

DISTRIBUTIONS AND CONTIGUITY

Svante Janson

Abstract. 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.

0. Introduction

In two remarkable papers, Robinson and Wormald [20], [21] have shown that asymptotically almost every random r-regular graph contains a Hamilton cycle for every fixed r ≥ 3. The purpose of this note is to show that their method of proof in fact gives more which is only implicit in their papers.

(We say here and below that “asymptotically almost every” graph has a property, or that a graph property holds “asymptotically almost surely” if the probability tends to 1 as the order of the graph increases; this is often called just “almost every” and “almost surely”, but we will in this paper reserve those terms for their usual measure theoretic meaning of probability equal to 1. Another equivalent term, used by some authors, is “with high probability”, whp.)

Robinson and Wormald actually give two different proofs of their result. We will draw further conclusions from both.

In [20] they prove the result for r = 3 using a conditioning and analysis of variance technique. As we will see below, this proof also gives the asymptotic distribution of the number of Hamilton cycles, which turns out to be rather complicated and neither normal nor log-normal. The method also applies to a number of related situations. We state these results in Section 1, deferring the proofs to Sections 6–7.

In [21], Robinson and Wormald use a different method for r ≥ 4. It is based on establishing a certain equivalence, known as contiguity, between two different models of random r-regular graphs. The two models have different distributions, but nevertheless, a property which holds asymptotically almost surely for one of the models also holds asymptotically almost surely for the other. (Events having a limiting probability strictly between 0 and 1 need not have the same limiting probability for the other model; contiguity means qualitative but not quantitative equivalence.) We believe that contiguity may be

Typeset by AMS-TEX

Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine

useful also for other problems in combinatorial probability theory, so we study the concept in some detail in Sections 2 and 3, giving both general results and specific examples for random graphs. We show that several models give contiguous distributions. In Section 4 we describe how these results give asymptotic distributions for functionals when we study random regular graphs with one of these distributions instead of the uniform one.

We let in this paper G(n, r) denote a random r-regular graph, drawn with uniform distribution from the set of all r-regular graphs on a fixed set of n labelled vertices. We assume always that n or r is even, and n ≥ r − 1, otherwise no such graphs exist. (There should be no risk of confusion with the notations G(n, p) and G(n, m) in this paper.) A random r-regular graph means always a graph with this, uniform, distribution, unless we explicitly specify another distribution.

We will often use multigraphs and prove versions of our results both for graphs and for multigraphs. One reason for doing this is that several of the proofs become easier in this greater generality.

Acknowledgement. This paper was begun during the conference on Random graphs and combinatorial structures in Oberwolfach in August 1993, and completed during a visit to the Institute for Mathematics and its Applications in Minneapolis later the same year. I thank several of the participants of these meetings, in particular Alan Frieze and Mark Jerrum, for helpful conversations. I am also grateful to Nick Wormald for helpful correspondence.

1. Asymptotic distributions.

As said above, the asymptotic distribution of the number of Hamilton cycles follows from the proof by Robinson and Wormald [20], which is based on conditioning and analysis of variance; see also Cooper, Frieze, Molloy and Reed [8] for comments and a partial reformulation of the argument. We set forth the main steps necessary to derive the asymptotic distribution as a general result.

Theorem 1. Let λ_{i} > 0 and δ_{i} ≥ −1, i = 1, 2, …, be constants and suppose that for each n there are random variables X_{in}, i = 1, 2, …, and Y_{n} (defined on the same probability space) such that X_{in} is non-negative integer valued and E Y_{n} ≠ 0 (at least for large n), and furthermore the following conditions are satisfied:

(A1) X_{in} ⟶^{d} Z_{i} as n → ∞, jointly for all i, where Z_{i} ∼ Po(λ_{i}) are independent Poisson

random variables; (A2) For any finite sequence x_{1}, …, x_{m} of non-negative integers,

\frac{E(Y_{n} | X_{1n} = x_{1}, …, X_{mn} = x_{m})}{E Y_{n}} → ∏_{i=1}^{m}(1 + δ_{i})^{x_{i}}e^{−λ_{i}δ_{i}} as n → ∞;

(A3) ∑_{i} λ_{i}δ_{i}^{2} < ∞;

(A4) \frac{E Y_{n}^{2}}{(E Y_{n})^{2}} → exp(∑_{i} λ_{i}δ_{i}^{2}) as n → ∞.

Then

\frac{Y_{n}}{E Y_{n}} ⟶^{d} W = ∏_{i=1}^{∞}(1 + δ_{i})^{Z_{i}}e^{−λ_{i}δ_{i}}  as n → ∞;  (1.1)

moreover, this and the convergence in A1 hold jointly. The infinite product defining W converges a.s. and in L^{2}, with E W = 1 and E W^{2} = exp(∑_{i} λ_{i}δ_{i}^{2}) = lim_{n→∞} E Y_{n}^{2}/(E Y_{n})^{2}.

Hence, the normalized variables Y_{n}/ E Y_{n} are uniformly square integrable. Furthermore, the event W > 0 equals, up to a set of probability zero, the event that Z_{i} > 0 for some i with δ_{i} = −1. In particular, W > 0 a.s. if and only if every δ_{i} > −1.

Remarks 1. We define 0^{0} = 1.

2. By joint convergence of an infinite number of variables we mean joint convergence of every finite subset, which is equivalent to convergence in R^{∞}.

3. We will often omit the “as n → ∞” in limits below, when there is no danger of confusion.

4. Condition A4 may be weakened to lim sup_{n→∞} E Y_{n}^{2}/(E Y_{n})^{2} ≤ exp(∑_{i} λ_{i}δ_{i}^{2}), since it follows from the proof in Section 5 that the other conditions imply lim inf_{n→∞} E Y_{n}^{2}/(E Y_{n})^{2} ≥ exp(∑_{i} λ_{i}δ_{i}^{2}).

5. The values of λ_{i} and δ_{i} are prescribed by A1 and A2. If sup_{n} E X_{in}^{2} < ∞ for each i, as is the case in all our applications, then {X_{in}}_{n} and {X_{in}Y_{n}/ E Y_{n}}_{n} are uniformly integrable (for fixed i) and we obtain (from the theorem or directly from A1 and A2)

E X_{in} → E Z_{i} = λ_{i}
E(X_{in}Y_{n}/ E Y_{n}) → E Z_{i}W = E Z_{i}(1 + δ_{i})^{Z_{i}}e^{−λ_{i}δ_{i}} = λ_{i}(1 + δ_{i})

and thus

λ_{i} = lim_{n→∞} E X_{in}
δ_{i} = lim_{n→∞} E(X_{in}Y_{n})/ E X_{in} E Y_{n} − 1.

6. The moments of W are easily computed:

E W^{m} = exp(∑_{i=1}^{∞} λ_{i}((1 + δ_{i})^{m} − 1 − mδ_{i})),  m > 0.  (1.2)

The sum converges for all m > 0 if, for example, sup δ_{i} < ∞. (If moreover inf δ_{i} > −1, (1.2) holds also for m < 0.) The conditions in the theorem do not in general imply convergence of higher moments than the second, but we conjecture that in the applications studied in this paper, for every fixed m > 0, E(Y_{n}/ E Y_{n})^{m} is bounded and thus converges to the value in (1.2) as n → ∞.

7. When W > 0 a.s., we obtain by (1.1)

log W = ∑_{j}(log(1 + δ_{j})Z_{j} − λ_{j}δ_{j})

= ∑_{j} log(1 + δ_{j})(Z_{j} − E Z_{j}) + α,

with α = ∑_{j} λ_{j}(log(1 + δ_{j}) − δ_{j}), and thus log W has the characteristic function

E e^{it log W} = exp(itα + ∑_{j} λ_{j}(e^{it log(1+δ_{j})} − 1 − it log(1 + δ_{j}))).

These equations show that log W has an infinitely divisible distribution with a discrete Lévy measure, cf. e.g. Loève [16].

8. If, for example, δ_{i} → 0 as i → ∞ with δ_{i} > −1, inf |δ_{i+1}/δ_{i}| > 0 and λ_{i}|δ_{i}|^{ϵ} → ∞ for some ϵ > 0, then it is easily shown that the characteristic function of log W is integrable and thus log W and W have absolutely continuous distributions, with continuous density functions. This is the case in all applications below, except that sometimes we have a δ_{i} = −1 and then the distribution of W has also a point mass at 0.

9. It follows from the proof that if we have two or several sequences of variables Y_{n}^{(j)}, each satisfying the conditions of the theorem (possibly with different δ_{i}^{(j)}) with the same variables X_{in}, then the Y_{n}^{(j)} converge jointly. It follows for example, by the uniform square integrability, that E Y_{n}^{(1)}Y_{n}^{(2)}/ E Y_{n}^{(1)} E Y_{n}^{(2)} → E W^{(1)}W^{(2)} = exp(∑_{i} λ_{i}δ_{i}^{(1)}δ_{i}^{(2)}).

10. For convenience, we use the index set {1,2, … } in Theorem 1, but we will without comment replace it by other countable index sets in applications.

We will in all our applications of Theorem 1 verify condition A2 by the method of moments argument used by Robinson and Wormald [20]. We state this step as a separate lemma. We let (X)_{k} denote the descending factorial X(X − 1) ⋯ (X − k + 1).

Lemma 1. Suppose that A1 holds, that Y_{n} ≥ 0 and that

(A2′)  E(Y_{n}(X_{in})_{j_{1}} ⋯ (X_{mn})_{j_{m}})/ E Y_{n} → ∏_{1}^{m} μ_{i}^{j_{i}}  as n → ∞,

for some μ_{i} ≥ 0 and every finite sequence j_{1}, …, j_{m} of non-negative integers. Then A2 holds with δ_{i} = μ_{i}/λ_{i} − 1.

We will prove Theorem 1 and Lemma 1 in Section 5. The idea of the proof of Theorem 1, following Robinson and Wormald [20] and Cooper, Frieze, Molloy and Reed [8], is to write Y_{n} = Y′_{n} + (Y_{n} − Y′_{n}), where Y′_{n} = E(Y_{n} | X_{1n}, X_{2n}, …). Then Var Y_{n} = Var Y′_{n} + Var(Y_{n} − Y′_{n}) by orthogonality (“analysis of variance”). Let us normalize to E Y_{n} = 1. Roughly speaking, the right hand side of A4 then equals the limit of 1 + Var Y′_{n}, and thus A4 says that almost all of the variance of Y_{n} comes from Y′_{n}, whence Var(Y_{n} −Y′_{n}) is small. Hence Y_{n} is well approximated by Y′_{n}, which in turn is well approximated by W by A2 and A1. (The detailed argument in Section 5 involves also a truncation.)

For Hamilton cycles, these general theorems yield the following result. (Proofs of this and the following theorems are given in Section 6.)

Theorem 2. Let r ≥ 3 be fixed and let H_{n} = H(G(n, r)) be the number of Hamilton cycles in a random r-regular graph on n vertices. Then

\frac{H_{n}}{E H_{n}} ⟶^{d} W = ∏_{\begin{matrix}i≥3 \\ i odd \end{matrix}}(1 − \frac{2}{(r − 1)^{i}} )^{Z_{i}}e^{1/i},  (1.3)

where Z_{i} ∼ Po(\frac{(r−1)^{i}}{2i} ) are independent Poisson random variables.

In this case

E H_{n} ∼ e\sqrt{\frac{π}{2n}}(\frac{(r − 2)^{(r−2)/2}(r − 1)}{r^{(r−2)/2}})^{n}  (1.4)

and

E H_{n}^{2}/(E H_{n})^{2} → e^{−2/(r−1)} \frac{r}{r − 2},  (1.5)

see [21].

The limiting random variable W in Theorem 2 is positive a.s. by Theorem 1. Hence the theorem implies

P(H_{n} ≥ 1) = P(H_{n}/ E H_{n} > 0) → P(W > 0) = 1,

so our theorem contains the result by Robinson and Wormald.

The limiting distribution in Theorem 2 is more complicated than the ones that usually appear in random graph theory. The Poisson variables Z_{i} that appear have, however, a simple interpretation as the numbers of small cycles in the random regular graph. More precisely, see Theorem 1 and Section 6, if we let X_{in} be the number of cycles of length i in the graph, then X_{in} ⟶^{d} Z_{i} as n → ∞, and this convergence in distribution holds jointly, for all i, together with H_{n}/ E H_{n} ⟶^{d} W. Hence the theorem can be interpreted as saying that H_{n}/ E H_{n} is, with large probability, well approximated by the infinite product with Z_{i} replaced by the small cycle count X_{in}, or rather by a finite product ∏_{1}^{N}(1 − 2/(r − 1)^{2k+1})^{X_{2k+1,n}}e^{1/(2k+1)}. (We have to let n → ∞ first and then N → ∞ in order to get convergence, because the factors e^{1/(2k+1)}, which are necessary convergence factors in (1.3), act as divergence factors for any finite n.)

It should perhaps not be surprising that H_{n} thus essentially is determined by the numbers of small cycles. Similar results hold for G(n, p) and G(n, m), where for certain ranges of p and m, log H_{n} is well approximated by a linear function of the number of edges, and of the number of paths of length 2, respectively, see [12]. Those results are simpler, however, since log H_{n} then is asymptotically normal, while in the present case log H_{n} − log E H_{n} converges to log W which has a rather complicated infinitely divisible distribution. Moreover, for G(n, p) and G(n, m) it suffices to use one small subgraph count in the approximation, whereas we here need an infinite sequence. (There are parallels to this in G(n, p) for other functionals, see e.g. [1], [11].)

Note that every small subgraph count for regular graphs can be essentially expressed in terms of small cycle counts, since asymptotically almost every random regular graph has no small multicyclic subgraphs. This explains why only cycle counts appear in Theorem 2 (as Z_{i}), but it seems mysterious that only the odd cycle counts appear, while the even cycle counts are asymptotically independent of H_{n}.

Theorem 1 applies also to several other, related, problems and we give some examples. First, recall that random regular graphs are simplest generated by the configuration

models of Bender and Canfield [2] or Bollobás [4], [5], which can be described as follows. Given r and a vertex set V with n elements (with rn even), define a configuration to be a perfect matching of the rn elements in V ×[r], where [r] = {1, …, r}. (We can call these rn elements half-edges.) Every configuration projects to an r-regular multigraph on V, and we define a random r-regular multigraph to be the projection of a randomly (uniformly) chosen configuration. It is easily seen that if we condition on there being no loops or multiple edges, we obtain a random r-regular graph G(n, r) with the usual uniform distribution. Note, however, that our random regular multigraphs are not uniformly distributed; the probability of obtaining a specified multigraph has a weight factor of 1/2 for every loop and 1/k! for every set of k parallel edges. Nevertheless, this model of a random regular multigraph seems to be the simplest and most useful.

We use G^{∗}(n, r) to denote a random regular multigraph (with this distribution). We let X_{in} be the number of cycles of length i ≥ 1 in our random multigraph, and observe that the multigraph is a graph if and only if X_{1n} = X_{2n} = 0. It is well-known that, as n → ∞, X_{in} ⟶^{d} Z_{i} ∼ Po (\frac{1}{2i}(r − 1)^{i}) jointly for i ≥ 1, with Z_{i} independent, and thus,

P(X_{1n} = X_{2n} = 0) → P(Z_{1} = Z_{2} = 0) = exp (−\frac{1}{2}(r − 1) − \frac{1}{4}(r − 1)^{2}) > 0;

see [5].

We may now extend Theorem 2 to multigraphs. In this and the following theorems, just as in Theorem 2, the variables Z_{i} are the limits of the cycle counts X_{in}.

Theorem 3. Let r ≥ 3 be fixed and let H_{n}^{∗} = H(G^{∗}(n, r)) be the number of Hamilton cycles in a random r-regular multigraph on n vertices. Then

\frac{H_{n}^{∗}}{E H_{n}^{∗}} ⟶^{d} W = ∏_{\begin{matrix}i≥1 \\ i odd \end{matrix}}(1 − \frac{2}{(r − 1)^{i}} )^{Z_{i}}e^{1/i},  (1.6)

where Z_{i} ∼ Po(\frac{(r−1)^{i}}{2i} ) are independent Poisson random variables.

For multigraphs we have, cf. (1.4) and (1.5)

E H_{n}^{∗} ∼ \sqrt{\frac{π}{2n}}(\frac{(r − 2)^{(r−2)/2}(r − 1)}{r^{(r−2)/2}})^{n}  (1.7)

and

E(H_{n}^{∗})^{2}/(E H_{n}^{∗})^{2} → \frac{r}{r − 2},  (1.8)

see Frieze, Jerrum and Molloy [9].

Note that the limit distribution for multigraphs in Theorem 3 differs from the one for graphs in Theorem 2 only by the additional factor (1 − \frac{2}{r−1})^{Z_{1}}e, where Z_{1} ∼ Po(\frac{r−1}{2}) should be interpreted as (the limit of) the number of 1-cycles, i.e. loops, in the multigraph.

If r ≥ 4, so that 1 − \frac{2}{r−1} > 0, then the limit W > 0 a.s. also in Theorem 3, and thus the theorem implies that asymptotically almost every r-regular multigraph contains a Hamilton cycle. On the other hand, if r = 3, then 1 − \frac{2}{r−1} = 0, and thus W = 0 when Z_{1} > 0 but, as before, W > 0 a.s. when Z_{1} = 0.

It follows from the joint convergence of (H_{n}^{∗}, X_{1n}) to (W, Z_{1}) that asymptotically almost every cubic multigraph is Hamiltonian if and only if it lacks loops, in the sense that as n → ∞, the probability tends to 0 that a random cubic multigraph has one of these properties but not the other. (One implication is obvious for all cubic multigraphs; the other holds only asymptotically.)

Furthermore, the joint convergence of (H_{n}^{∗}, X_{1n}, X_{2n}) and the fact that P(Z_{1} = Z_{2} = 0) > 0 imply that the limit in Theorem 3 remains true if we condition on X_{1n} = X_{2n} = 0, i.e.

L (\frac{H_{n}^{∗}}{E H_{n}^{∗}} | X_{1n} = X_{2n} = 0) ⟶^{d} L(W | Z_{1} = Z_{2} = 0) = L(e ∏_{\begin{matrix}i≥3 \\ i odd \end{matrix}}(1 − \frac{2}{(r − 1)^{i}} )^{Z_{i}}e^{1/i}).

The left hand side is the distribution of the number H_{n} = H(G(n, r)) of Hamilton cycles in a random regular graph, normalized by the expectation E H_{n}^{∗} for the random multigraph. Since the uniform integrability of H_{n}^{∗}/ E H_{n}^{∗} (see Theorem 1) survives the conditioning,

E H_{n}/ E H_{n}^{∗} = E(H_{n}^{∗} | X_{1n} = X_{2n} = 0)/ E H_{n}^{∗} → E(W | Z_{1} = Z_{2} = 0) = e,

and we recover Theorem 1 as a corollary to Theorem 3.

For future reference we observe that we can use this conditioning argument in all cases where Theorem 1 applies. We obtain, if Y′_{n} has the distribution of Y_{n} conditioned on X_{1n} = X_{2n} = 0,

E Y′_{n}/ E Y_{n} → E(W | Z_{1} = Z_{2} = 0) = exp(−λ_{1}δ_{1} − λ_{2}δ_{2})  (1.9)

and similarly

E(Y′_{n})^{2}/(E Y_{n})^{2} → E(W^{2} | Z_{1} = Z_{2} = 0) = exp(−2λ_{1}δ_{1} − 2λ_{2}δ_{2} + ∑_{i=3}^{∞} λ_{i}δ_{i}^{2}); (1.10)

combining these we obtain

E(Y′_{n})^{2}/(E Y′_{n})^{2} → exp(∑_{i=3}^{∞} λ_{i}δ_{i}^{2}) = exp(−λ_{1}δ_{1}^{2} − λ_{2}δ_{2}^{2}) E W^{2},  (1.11)

For the Hamilton cycles in Theorem 3 we have δ_{1} = −2/(r −1), δ_{2} = 0 and λ_{1} = (r −1)/2, and we see that (1.9) and (1.11) yield (1.4) and (1.5) from (1.7) and (1.8).

As said above, the proof of Theorem 2 is based on the proof that P(H_{n} > 0) → 1 for r = 3 by Robinson and Wormald [20]. In [21] they prove the result for r ≥ 4 by another method, which does not give the information on the distribution that we need. One step in that proof, however, is to use the method of [20] to prove a result on the number M of perfect matchings. Again, their proof contains implicitly the asymptotic distribution.

Theorem 4. Let M_{n}^{∗} = M(G^{∗}(n, r)) be the number of perfect matchings in a random r-regular multigraph. Then, if r ≥ 3 is fixed and n is even,

\frac{M_{n}^{∗}}{E M_{n}^{∗}} ⟶^{d} W = ∏_{i=1}^{∞} (1 + \frac{(−1)^{i}}{(r − 1)^{i}} )^{Z_{i}} e^{(−1)^{i−1}/2i},

where Z_{i} ∼ Po (\frac{(r−1)^{i}}{2i} ) are as in Theorems 1 and 3. Similarly, for graphs, with M_{n} = M(G(n, r)),

\frac{M_{n}}{E M_{n}} ⟶^{d} ∏_{i=3}^{∞} (1 + \frac{(−1)^{i}}{(r − 1)^{i}} )^{Z_{i}} e^{(−1)^{i−1}/2i}.

For matchings,

E M_{n}^{∗} ∼ \sqrt{2} (\frac{(r − 1)^{(r−1)/2}}{r^{(r−2)/2}} )^{n}  (1.12)

and

E(M_{n}^{∗})^{2}/(E M_{n}^{∗})^{2} → \sqrt{\frac{r − 1}{r − 2}}  (1.13)

while (1.9) and (1.11) yield E M_{n} ∼ e^{1/4} E M_{n}^{∗} and

E M_{n}^{2}/(E M_{n})^{2} → e^{−(2r−1)/4(r−1)^{2}} E(M_{n}^{∗})^{2}/(E M_{n}^{∗})^{2},  (1.14)

cf. [6] and [21].

As for Theorems 1 and 3, Z_{i} can be interpreted (asymptotically) as the number of cycles of length i. Note that now cycles of all lengths appear, and that the number of perfect matchings is positively correlated with the even cycle counts but negatively correlated with the odd ones.

In Theorem 4, every δ_{i} > −1, and thus W > 0 a.s. and we obtain as a corollary the well-known result that asymptotically almost every r-regular (multi-)graph of even order contains a perfect matching when r ≥ 3.

Remark 9 implies that H_{n}^{∗} and M_{n}^{∗} converge jointly to the limits in Theorems 3 and 4; moreover,

E H_{n}^{∗}M_{n}^{∗}/ E H_{n}^{∗} E M_{n}^{∗} → exp( ∑_{i odd} λ_{i} \frac{−2}{(r − 1)^{i}} \frac{−1}{(r − 1)^{i}} ) = \sqrt{\frac{r}{r − 2}}.  (1.15)

Instead of studying just single perfect matchings in an r-regular graph, we may try to decompose it into an r-tuple of perfect matchings. For any r-regular multigraph G^{∗}, let U(G^{∗}) be the number of partitions of the edge set of G^{∗} into r perfect matchings M_{1}, …, M_{r}. To be specific, we distinguish between different orderings of M_{1}, …, M_{r}, and we regard parallel edges in G^{∗} as distinguishable. We may also say that U(G^{∗}) is the number of r-colourings of the edges in G^{∗} such that each colour class is a perfect matching. We believe that the following result holds for any r ≥ 3, but we have only been able to prove it for r = 3.

Theorem 5. Let U_{n}^{∗} = U(G^{∗}(n, r)) and U_{n} = U(G(n, r)). If r = 3, then (for even n)

\frac{U_{n}^{∗}}{E U_{n}^{∗}} ⟶^{d} ∏_{i=1}^{∞} (1 − \frac{1}{(r − 1)^{i−1}} )^{Z_{i}} e^{(r−1)/2i}

and

\frac{U_{n}}{E U_{n}} ⟶^{d} ∏_{i=3}^{∞} (1 − \frac{1}{(r − 1)^{i−1}} )^{Z_{i}} e^{(r−1)/2i},

where Z_{i} ∼ Po (\frac{(r−1)^{i}}{2i} ) are as above.

The asymptotics of the expectations and variances are given in Section 6. Note that in this case, δ_{1} = −(r − 1)^{0} = −1 while δ_{i} > −1 for i ≥ 2; hence we obtain as a corollary that asymptotically almost every cubic multigraph without loops has a decomposition into perfect matchings. (Of course, a loop always prevents such a decomposition.) This is true for any r ≥ 3, as was proved (for graphs) by Robinson and Wormald [20], [21]; we will prove a stronger statement in Theorem 11 below. See also Molloy, Robalewska-Szarłat, Robinson and Wormald [17].

There are also analogous results for some related random structures.

Let us first consider a random regular bipartite graph B(n, r) (on n + n vertices) or the corresponding random multigraph B^{∗}(n, r). As for G(n, r), these are obtained from random configurations; the allowed configurations now are perfect matchings between two disjoint sets V_{1} × [r] and V_{2} × [r] of cardinality rn. In this case, for the small cycle counts,

X_{in} ⟶^{d} Z_{i} ∼ Po (\frac{(r − 1)^{i}}{i} )  as n → ∞,  (1.16)

for even i (i ≥ 2 for B^{∗}(n, r) and i ≥ 4 for B(n, r)); of course, X_{in} = 0 when i is odd. For perfect matchings, there is an analogue to Theorem 4.

Theorem 6. Let M_{n}^{∗} = M(B^{∗}(n, r)). If r ≥ 3, then

\frac{M_{n}^{∗}}{E M_{n}^{∗}} ⟶^{d} ∏_{\begin{matrix}i≥2 \\ i even \end{matrix}} (1 + \frac{1}{(r − 1)^{i}} )^{Z_{i}} e^{−1/i}.

For M(B(n, r)), we get the same result with i ≥ 4 in the product.

We have

E M_{n}^{∗} ∼ (\frac{2π(r − 1)n}{r})^{1/2} (\frac{(r − 1)^{r−1}}{r^{r−2}} )^{n}  (1.17)

and

E(M_{n}^{∗})^{2}/(E M_{n}^{∗})^{2} → \frac{r − 1}{\sqrt{r(r − 2)}};  (1.18)

the corresponding results for B(n, r) follow by (1.9) and (1.11), cf. Bollobas and McKay [6].

For Hamilton cycles in the bipartite case, it has been shown by Robinson and Wormald [19] that for r = 3, with H_{n} = H(B(n, r)), E H_{n}^{2}/(E H_{n})^{2} → 1 and thus H_{n}/ E H_{n} ⟶^{p} 1. We believe that the same holds for any r > 3 and also for B^{∗}(n, r), r ≥ 3, but as far as we know this has not yet been verified. Note that this result, although strikingly different from Theorem 1, still fits nicely together with it, since the variation in Theorem 1 comes from the randomness in the small odd cycle counts, whereas there are no odd cycles in a bipartite graph. (That asymptotically almost every r-regular bipartite graph contains a Hamilton cycle when r ≥ 3 was proved by Robinson and Wormald [21].)

The theory also applies to the random r-regular digraph D(n, r) (also known as rin, r-out), and the corresponding directed multigraph D^{∗}(n, r). We can construct these by a configuration model with 2r half-edges for each vertex, r labeled “in” and r labeled “out”, or, equivalently, by taking a random bipartite (multi-)graph with vertex set V_{1} ∪V_{2}, orienting all edges from V_{1} to V_{2} and then identifying V_{1} and V_{2} (by a fixed identification).

For directed graphs, we again use the numbers of small cycles in the limit theorems, but we now consider cycles of any possible orientation. If C is a k-cycle with oriented edges, let k_{i}, i = 0, 1, 2, be the numbers of vertices with out-degree i in C. Clearly, k_{2} = k_{0} and k_{0} + k_{1} + k_{2} = k. Let X_{Cn} be the number of copies of C in D^{∗}(n, r). Then, by standard arguments,

E X_{Cn} = \frac{(n)_{k}(r(r − 1))^{k_{0}+k_{2}}r^{2k_{1}}}{aut(C)(rn)_{k}} → λ_{C} = \frac{1}{aut(C)}r^{k_{1}}(r − 1)^{k_{0}+k_{2}},  (1.19)

where aut(C) is the number of automorphisms of C, and

X_{Cn} ⟶^{d} Z_{C} ∼ Po(λ_{C}),  (1.20)

jointly in all C, with Z_{C} independent.

With some foresight, we introduce special notation for two classes of oriented cycles, viz. C_{k}, k ≥ 1, for the directed cycle of length k and C_{k}^{a}, k ≥ 2 even, for the cycle of length k with alternating directions. (These are the cycles with all and no vertices of out-degree 1, respectively.) By (1.19) we have

λ_{C_{k}} = \frac{r^{k}}{k}  (1.21)

and, for even k,

λ_{C_{k}^{a}} = \frac{(r − 1)^{k}}{k} .  (1.22)

For simplicity, we state the results for random directed multigraphs only. The corresponding results for directed graphs follow by conditioning on Z_{C_{2}^{a}} = 0, or Z_{C_{1}} = Z_{C_{2}^{a}} = 0, or Z_{C_{1}} = Z_{C_{2}} = Z_{C_{2}^{a}} = 0, depending on what we regard as a directed graph; we leave the details to the reader.

Theorem 7. Let H_{n} = H(D^{∗}(n, r)) be the number of Hamilton cycles in a random rregular directed multigraph. If r ≥ 3, then

\frac{H_{n}}{E H_{n}} ⟶^{d} ∏_{k=1}^{∞} (1 − \frac{1}{r^{k}} )^{Z_{C_{k}}} e^{1/k} ∏_{\begin{matrix}j=2 \\ j even \end{matrix}}^{∞} (1 + \frac{1}{(r − 1)^{j}} )^{Z_{C^{a}_{j}}} e^{−1/j},

where Z_{C} ∼ Po(λ_{C}) are independent.

We here have

E H_{n} ∼ \sqrt{\frac{2π(r − 1)}{rn}} (\frac{(r − 1)^{r−1}}{r^{r−2}} )^{n}  (1.23)

and

E H_{n}^{2}/(E H_{n})^{2} → \sqrt{\frac{r}{r − 2}}.  (1.24)

Again, the limit in the theorem is > 0 a.s., and thus we obtain as a corollary the result by Cooper, Frieze and Molloy [7] that asymptotically almost every r-regular directed (multi)- graph is Hamiltonian, r ≥ 3.

Another interesting quantity in a directed graph is the number of permutations, or 1-regular subgraphs. Note that the correspondence between bipartite graphs and directed graphs induces a correspondence between perfect matchings and permutations; moreover, cycles in the bipartite graph correspond to alternating cycles in the directed graph, except in the improbable cases where vertices coincide.

Hence the following theorem is just a reformulation of Theorem 6.

Theorem 8. Let V_{n} = V (D^{∗}(n, r)) be the number of permutations in a random r-regular directed multigraph. If r ≥ 3, then

\frac{V_{n}}{E V_{n}} ⟶^{d} ∏_{\begin{matrix}j≥2 \\ j even \end{matrix}} (1 + \frac{1}{(r − 1)^{j}} )^{Z_{C^{a}_{j}}} e^{−1/j},

where Z_{C_{j}^{a}} ∼ Po(λ_{C_{j}^{a}}) are as above.

The expectation and second moment are given by (1.17) and (1.18).

Finally, we give an application to random regular hypergraphs. Cooper, Frieze, Molloy and Reed [8] have generalized the proof in [21] on existence of perfect matchings to regular hypergraphs. Again, their proof yields the asymptotic distribution. We refer to [8] for definitions.

Theorem 9. Let s ≥ 3 and r be fixed, with r so large that log r/(r − 1) log \frac{r}{r−1} + 1 > s. If Y is the number of perfect matchings in a random r-regular s-uniform hypergraph, then

\frac{Y}{E Y} ⟶^{d} W = ∏_{i=2}^{∞} (1 + \frac{(−1)^{i}}{(r − 1)^{i}} )^{Z_{i}} e^{−(1−s)^{i}/2i}

where Z_{i} ∼ Po (\frac{1}{2i}((r − 1)(s − 1))^{i}) are independent.

2. Contiguity in general

Definition. Let (P_{n})_{1}^{∞} and (Q_{n})_{1}^{∞} be two sequences of probability measures, such that for each n, P_{n} and Q_{n} both are defined on the same measurable space (Ω_{n}, F_{n}). We then say that the sequences are contiguous if for every sequence of measurable sets A_{n} ⊂ Ω_{n},

lim_{n→∞} P_{n}(A_{n}) = 0 ⟺ lim_{n→∞} Q_{n}(A_{n}) = 0.  (2.1)

Clearly, contiguity is an equivalence relation among sequences of probability measures on a given sequence of space (Ω_{n}). Its use is mainly in statistics, but it seems to be natural and useful also in the study of random combinatorial structures. In that case, typically, Ω_{n} is a (finite) set of some combinatorial objects of size n, F_{n} is the σ-field of all subsets of Ω_{n}, and P_{n} and Q_{n} are probability measures corresponding to two different ways of selecting an element of Ω_{n} “at random”.

This notion was introduced by Le Cam [13], see also Le Cam [14], [15] and Roussas [22]. We will here consider only the symmetric version of contiguity defined above, although the corresponding one-sided notion has been studied as well, see [15].

There are many equivalent definitions of contiguity; some are given below and several others are given in the references given above. For completeness we will include proofs even when our results can be found in these references.

It is important to realize that contiguity is an asymptotic property of two sequences of probability measures; if we say that two probability measures (or distributions, or random models) are contiguous, we really mean that there is some parameter n (although perhaps not explicitly mentioned) that tends to infinity. If we, as is often useful, informally regard asymptotic results as statements about a fictitious infinite limiting model, then contiguity can be interpreted as mutual absolute continuity of the two probability measures. (In this context it may be observed that in the special case that Ω_{n}, F_{n}, P_{n} and Q_{n} do not depend on n, contiguity reduces to mutual absolute continuity.)

Note also that the definition says nothing about the rates of convergence of P_{n}(A_{n}) and Q_{n}(A_{n}); these may be quite different. It is, nevertheless, possible to restate the definition in terms of estimates, which, however, use unknown functions to relate the rates. (In certain examples, it may of course be possible to replace these by explicit functions.) We given two such reformulations, which we think may be useful for a better understanding the contiguity concept.

Proposition 1. The sequences (P_{n}) and (Q_{n}) are contiguous if and only if there exist a sequence ε_{n} → 0 and a continuous function φ : [0, 1] → [0, 1] with φ(0) = 0 such that for every n and A_{n} ∈ F_{n}

P_{n}(A_{n}) ≤ ε_{n} + φ(Q_{n}(A_{n}))  and  Q_{n}(A_{n}) ≤ ε_{n} + φ(P_{n}(A_{n})).  (2.2)

Proof. If (P_{n}) and (Q_{n}) are contiguous, then for every ε > 0 there exist n(ε) and δ(ε) such that n ≥ n(ε) and P_{n}(A_{n}) ≤ δ(ε) ⇒ Q_{n}(A_{n}) ≤ ε, and similarly with P_{n} and Q_{n} interchanged. The existence of (ε_{n}) and φ now follows easily. The converse is obvious. □

For the next results, we recall that each Q_{n} has a Lebesgue decomposition Q_{n} = Q_{n}^{a}+Q_{n}^{s} where Q_{n}^{a} is absolutely continuous with respect to P_{n} while Q_{n}^{s} and P_{n} are mutually singular, and that there exists a function dQ_{n}/dP_{n} ≥ 0 (the Radon-Nikodym derivative) such that

Q_{n}^{a}(A_{n}) = ∫_{A_{n}} \frac{dQ_{n}}{dP_{n}} dP_{n}, A_{n} ∈ F_{n}.

(If Ω_{n} is countable, the measures are given by probability functions p_{n}(w) and q_{n}(w); in this case Q_{n}^{s} is the restriction of Q_{n} to the set {w : p_{n}(w) = 0}, while dQ_{n}/dP_{n} = q_{n}(w)/p_{n}(w) when p_{n}(w) ≠ 0 (and arbitrary otherwise).)

Proposition 2. The sequences (P_{n}) and (Q_{n}) are contiguous if and only if for every ε > 0 there exist n(ε) and K(ε) such that for every n ≥ n(ε) there exists a set B_{n} ∈ F_{n} with P_{n}(B_{n}^{c}) ≤ ε, Q_{n}(B_{n}^{c}) ≤ ε such that

K(ε)^{−1} ≤ \frac{Q_{n}(A_{n})}{P_{n}(A_{n})} ≤ K(ε)  for all A_{n} ⊆ B_{n}.  (2.3)

Remark 11. We may here replace (2.3) by the equivalent condition that the restriction of Q_{n} to B_{n} is absolutely continuous with respect to P_{n}, with

K(ε)^{−1} ≤ \frac{dQ_{n}}{dP_{n}} ≤ K(ε)  P_{n}-a.s. on B_{n}.  (2.4)

Proof. Suppose that (P_{n}) and (Q_{n}) are contiguous. Fix a large number K, let C_{n} be a set such that P_{n}(C_{n}) = 0 = Q_{n}^{s}(C_{n}^{c}) (this is possible by the definition of singular measures), and define

D_{n} = {w ∈ Ω_{n} : dQ_{n}/dP_{n} > K}.

Then

P_{n}(C_{n} ∪ D_{n}) = ∫_{D_{n}} dP_{n} ≤ \frac{1}{K} ∫_{D_{n}} \frac{dQ_{n}}{dP_{n}} dP_{n} = \frac{1}{K} Q_{n}^{a}(D_{n}) ≤ \frac{1}{K} .

Hence Proposition 1 yields Q_{n}(C_{n} ∪ D_{n}) ≤ ε_{n} + φ(K^{−1}). Furthermore, for any A_{n} ⊆ (C_{n} ∪ D_{n})^{c},

Q_{n}(A_{n}) = Q_{n}^{a}(A_{n}) = ∫_{A_{n}} \frac{dQ_{n}}{dP_{n}} dP_{n} ≤ KP_{n}(A_{n}).

We similarly define C′_{n} and D′_{n} with the roles of P_{n} and Q_{n} interchanged, and let B_{n} = (C_{n} ∪ D_{n} ∪ C′_{n} ∪ D′_{n})^{c}. Then P_{n}(B_{n}^{c}), Q_{n}(B_{n}^{c}) ≤ K^{−1} + ε_{n} + φ(K^{−1}), which is less than ε for n ≥ n(ε) if n(ε) and K = K(ε) are large enough.

Conversely, if such sets B_{n} exist, then for large n and every A_{n} ∈ F_{n},

Q_{n}(A_{n}) ≤ Q_{n}(A_{n} ∩ B_{n}) + Q_{n}(B_{n}^{c}) ≤ K(ε)P_{n}(A_{n}) + ε.

In particular, if P_{n}(A_{n}) → 0, then lim sup Q_{n}(A_{n}) ≤ ε, for every ε > 0, and thus Q_{n}(A_{n}) → 0. By symmetry, we obtain also the converse implication and thus the sequences are contiguous. □

For the next result, we consider for simplicity only the case when dQ_{n}/dP_{n} converges in distribution.

Proposition 3. Suppose that L_{n} = dQ_{n}/dP_{n}, regarded as a random variable on (Ω_{n}, F_{n}, P_{n}), converges in distribution to some random variable L as n → ∞. Then (P_{n}) and (Q_{n}) are contiguous if and only if L > 0 a.s. and E L = 1.

Proof. Suppose that (P_{n}) and (Q_{n}) are contiguous. Let ε > 0, and let K(ε) and B_{n}, n ≥ n(ε), be as in Proposition 2. In particular, by Remark 11, K(ε)^{−1} ≤ L_{n} ≤ K(ε) on B_{n}. Thus

P(L = 0) ≤ P(L < K(ε)^{−1}) ≤ lim sup_{n→∞} P_{n}(L_{n} < K(ε)^{−1}) ≤ lim sup_{n→∞} P_{n}(B_{n}^{c}) ≤ ε.

Moreover, since L_{n} ∧ K(ε) ⟶^{d} L ∧ K(ε) as n → ∞, dominated convergence yields

E L ≥ E(L ∧ K(ε)) = lim_{n→∞} ∫_{Ω_{n}} L_{n} ∧ K(ε) dP_{n} ≥ lim sup_{n→∞} ∫_{B_{n}} L_{n} dP_{n} = lim sup_{n→∞} Q_{n}(B_{n})
≥ 1 − ε.

Since ε is arbitrary, P(L = 0) = 0 and E L = 1.

Conversely, suppose that P(L = 0) = 0 and E L = 1, and let ε > 0. There exists δ > 0 such that P(L ≤ δ) < ε; we may furthermore choose δ such that δ < 1 and P(L = δ) = 0. Then P_{n}(L_{n} ≤ δ) → P(L ≤ δ), and thus P_{n}(L_{n} ≤ δ) < ε for large n, which also yields Q_{n}^{a}(L_{n} ≤ δ) = ∫_{L_{n}≤δ} L_{n} dP_{n} < εδ ≤ ε.

We can also find K > 1/ε such that E(L∧K) > 1−ε and thus lim_{n→∞} ∫ (L_{n}∧K)dP_{n} = E(L ∧ K) > 1 − ε. Hence, for large n, say n ≥ n(ε),

ε > 1 − ∫_{Ω_{n}}(L_{n} ∧ K)dP_{n} = Q_{n}^{s}(Ω_{n}) + Q_{n}^{a}(Ω_{n}) − ∫_{Ω_{n}}(L_{n} ∧ K)dP_{n}
= Q_{n}^{s}(Ω_{n}) + ∫_{Ω_{n}}(L_{n} − L_{n} ∧ K)dP_{n} ≥ Q_{n}^{s}(Ω_{n}) + \frac{1}{2} ∫_{L_{n}>2K} L_{n} dP_{n}
= Q_{n}^{s}(Ω_{n}) + \frac{1}{2}Q_{n}^{a}(L_{n} > 2K).

Let N_{n} be a set with P_{n}(N_{n}) = Q_{n}^{s}(N_{n}^{c}) = 0, and define B_{n} = {w ∈ N_{n}^{c} : δ ≤ L_{n} ≤ 2K}. Then, for n ≥ n(ε),

P_{n}(B_{n}^{c}) = P_{n}(L_{n} < δ) + P_{n}(L_{n} > 2K) < ε + ∫ L_{n} dP_{n}/2K < 2ε

and

Q_{n}(B_{n}^{c}) = Q_{n}^{s}(Ω_{n}) + Q_{n}^{a}(L_{n} < δ) + Q_{n}^{a}(L_{n} > 2K) < 3ε.

Hence Proposition 2 implies that (P_{n}) and (Q_{n}) are contiguous. □

Contiguity is preserved by some natural operations, as the next proposition shows. In (ii) and (iii) we suppose that (Ω′_{n}, F′_{n}) is another sequence of measure spaces.

Proposition 4. Suppose that (P_{n}) and (Q_{n}) are contiguous.

(i) If (A_{n}) is any sequence of events such that lim inf P_{n}(A_{n}) > 0, then the conditioned measures P_{n}(· | A_{n}) and Q_{n}(· | A_{n}) are contiguous.

(ii) If f_{n} : Ω_{n} → Ω′_{n} are measurable functions, then the induced measures P_{n} ∘f_{n}^{−1} and

Q_{n} ∘ f_{n}^{−1} on Ω′_{n} are contiguous. (iii) If P′_{n} and Q′_{n} are contiguous probability measures on Ω′_{n}, then the product measures

P_{n} × P′_{n} and Q_{n} × Q′_{n} on Q_{n} × Q′_{n} are contiguous.

Proof. (i) and (ii) follow easily from the definition (note that also lim inf Q_{n}(A_{n}) > 0 in (i)); for (iii) it is perhaps simplest to use Proposition 2 with Remark 11. We omit the details. □

Contiguity of two sequences (P_{n}) and (Q_{n}) has several useful consequences for limit theorems. The definition says that any property which holds under P_{n} with probability tending to 1 as n → ∞ (i.e., asymptotically almost surely) also holds under Q_{n} with probability tending to 1 (and conversely). An immediate consequence is that if X_{n} are any random variables such that X_{n} under P_{n} converges in probability to some constant c, then X_{n} converges in probability to the same constant c also under Q_{n}.

For convergence in distribution we need some further information. In the three next results we suppose that S and S′ are two complete separable metric spaces, for example R, R^{d} or the space R^{∞} of infinite sequences. (See [3] for details on convergence in metric spaces.) We use L(X | P) to denote the distribution of X under P.

In the first result we assume joint convergence under P_{n} of the variables X_{n} and the Radon–Nikodym derivatives dQ_{n}/dP_{n}.

Proposition 5. Suppose that (P_{n}) and (Q_{n}) are contiguous, and let L_{n} = dQ_{n}/dP_{n}. Suppose further that X_{n} are random variables defined on Ω_{n} with values in S, such that L((X_{n}, L_{n}) | P_{n}) → L(X, L) for some random variables X and L (with values in S and R respectively), defined on a probability space (Ω, F, P). Then L(X_{n} | Q_{n}) → L(X | Q), where dQ = L dP (i.e., Q(A) = ∫_{A} L dP).

Proof. Let f be a bounded continuous real-valued function on S. Then L(f(X_{n})L_{n} | P_{n}) → L(f(X)L). If f ≥ 0, then Fatou’s lemma yields

lim inf ∫ f(X_{n})L_{n} dP_{n} ≥ ∫ f(X)L dP.  (2.5)

Since ∫ L_{n} dP_{n} → ∫ L dP by Proposition 3, we see, by adding a constant to f, that (2.5) actually holds for every f. But then we may also substitute −f in (2.5), and obtain

∫ f(X_{n}) dQ_{n}^{a} = ∫ f(X_{n})L_{n} dP_{n} → ∫ f(X)L dP = ∫ f(X) dQ.  (2.6)

Since also Q_{n}^{s}(Ω_{n}) → 0, which for example follows from (2.6) with f = 1, we obtain

∫ f(X_{n}) dQ_{n} → ∫ f(X) dQ

for every such f, which gives the result. □

Proposition 6. Suppose that (P_{n}) and (Q_{n}) are contiguous. Suppose further that X_{n} and Y_{n} are random variables defined on Ω_{n}, with values in S and S′ respectively, such that

L((X_{n}, Y_{n}) | P_{n}) → L(X, f(X))  (2.7)

for some random variable X with values in S and some measurable function f : S → S′. If, furthermore, L(X_{n} | Q_{n}) → L(X′) for some other random variable X′, then L((X_{n}, Y_{n}) | Q_{n}) → L(X′, f(X′)); in particular L(Y_{n} | Q_{n}) → L(f(X′)).

Proof. Let L_{n} = dQ_{n}/dP_{n}. The assumption implies by Prohorov’s theorem, see [3], that {L((X_{n}, Y_{n}) | P_{n})} is a tight family of distributions on S × S′. Since also the family {L(L_{n} | P_{n})} is tight, because ∫ L_{n}dP_{n} ≤ 1, the family {L((X_{n}, Y_{n}, L_{n}) | P_{n})} is tight on S × S′ × R. By Prohorov’s theorem again, there exists a subsequence that converges in distribution to some variable (X̃, Ỹ, L). Obviously L(X̃, Ỹ) = L(X, f(X)), and thus Ỹ = f(X̃) a.s. Moreover, we may use Proposition 5 on (X_{n}, Y_{n}) along the subsequence and conclude

L((X_{n}, Y_{n}) | Q_{n}) → L((X̃, Ỹ) | Q) = L((X̃, f(X̃)) | Q).

Since also, by assumption, L(X_{n} | Q_{n}) → L(X′), we have L(X̃ | Q) = L(X′) and thus L((X̃, f(X̃)) | Q) = L(X′, f(X′)). Consequently, L((X_{n}, Y_{n}) | Q_{n}) → L(X′, f(X′)) along the subsequence.

We have proved that the sought conclusion holds at least along a subsequence. But the same applies to every subsequence of the original sequence, which thus has a subsubsequence for which L((X_{n}, Y_{n}) | Q_{n}) → L(X′, f(X′)). This implies that the full sequence converges. □

The next result gives a necessary condition for contiguity.

Proposition 7. Suppose that (P_{n}) and (Q_{n}) are contiguous, and that X_{n} are random variables defined on Ω_{n} with values in S. Suppose further that (X_{n}) converges in distribution under both (P_{n}) and (Q_{n}):

L(X_{n} | P_{n}) → P_{X}  and  L(X_{n} | Q_{n}) → Q_{X}

for two probability measures P_{X} and Q_{X} on S. Then P_{X} and Q_{X} are mutually absolutely continuous.

Proof. Let L_{n} = dQ_{n}/dP_{n}. Since E L_{n} ≤ 1, the sequence (L_{n}) is tight and we may, by restricting attention to a subsequence, assume that L((X_{n}, L_{n}) | P_{n}) converges. Proposition 5 now implies that Q_{X} is absolutely continuous with respect to P_{X}. The converse holds by symmetry. □

We will use Proposition 7 in conjunction with the following standard result. (In fact, the given conditions are equivalent to mutual absolute continuity.)

Proposition 8. Suppose that the measure ∏_{i} Po(λ_{i}) and ∏_{i} Po(λ′_{i}) on Z^{∞} are mutually absolutely continuous. Then

λ_{i} = 0 ⟺ λ′_{i} = 0,

and

∑_{i} \frac{(λ_{i} − λ′_{i})^{2}}{λ_{i} + λ′_{i}} < ∞.

Proof. The first conclusion is trivial. For the second, we may use the Hellinger integral, defined for any two probability measures μ and μ′ on the same space by I(μ, μ′) = ∫ (\frac{dμ}{dν} \frac{dμ′}{dν} )^{1/2}dν, where ν is any σ-finite measure with μ, μ′ ≪ ν. It is easily seen that μ and μ′ are mutually singular if and only if I(μ, μ′) = 0, and that in our case

I (∏_{i} Po(λ_{i}), ∏_{i} Po(λ′_{i})) = ∏_{i} I(Po(λ_{i}), Po(λ′_{i})) = ∏_{i} e^{−(\sqrt{λ_{i}}−\sqrt{λ′_{i}})^{2}/2}.

Hence the measures are mutually singular unless

∞ > ∑(\sqrt{λ_{i}} − \sqrt{λ′_{i}})^{2} = ∑(λ_{i} − λ′_{i})^{2}/(\sqrt{λ_{i}} + \sqrt{λ′_{i}})^{2} ≥ \frac{1}{2} ∑(λ_{i} − λ′_{i})^{2}/(λ_{i} + λ′_{i}). □

3. Contiguity for regular graphs

The results of Sections 1 and 2 may now be combined to yield various examples of contiguity. To begin with, let us again consider the number H_{n}^{∗} of Hamilton cycles in a random r-regular multigraph. Let Ω_{n} be the set of all r-regular multigraphs on the set V = [n], let the probability measure P_{n} on Ω_{n} be the distribution of the random multigraph G^{∗}(n, r), and define a new probability measure Q_{n} on Ω_{n} by dQ_{n}/dP_{n} = H_{n}^{∗}/ E H_{n}^{∗}, i.e., Q_{n}(A) = E(H_{n}^{∗}1_{A})/ E H_{n}^{∗} for any set A ⊆ Ω_{n}, where 1_{A} is the indicator function. Then Theorem 3 and Proposition 3 imply that if r ≥ 4 then (P_{n}) and (Q_{n}) are contiguous. (Recall that we need r ≥ 4 in order to have W > 0 a.s. in Theorem 3 and that E W = 1 by Theorem 1.)

The measure Q_{n} has the following interpretation. Consider the set \overline{Ω}_{n} of all pairs (G̃, H̃) of a configuration G̃ (on nr half-edges) and a set H̃ of edges in G̃ that projects to a Hamilton cycle in the multigraph G^{∗} obtained by projecting G̃. Pick one of these pairs (G̃, H̃) at random, uniformly over \overline{Ω}_{n}, and take the projection G^{∗}. This defines a random r-regular multigraph which has the distribution Q_{n}, since the probability of obtaining a specific multigraph G^{∗} is proportional to the number of pairs (G̃, H̃) ∈ \overline{Ω} projecting to G^{∗}, which is proportional to P_{n}(G^{∗})H(G^{∗}). Furthermore, by symmetry, we obtain the same distribution Q_{n} by picking the pair (G̃, H̃) at random in the subset \overline{Ω}′_{n} of all such pairs (G̃, H̃) such that the edges in H̃ join half-edges in V × {1, 2}. But these pairs are just the pairs (H̃ ∪H̃′, H̃), where H̃ is a configuration on V ×{1, 2} projecting to a Hamilton cycle and H̃′ is any configuration on V × \{3, …, r\}. Picking an element in \overline{Ω}′ at random is thus the same as picking such H̃ and H̃′ independently at random, and after projecting we see that Q_{n} equals the distribution of the union of a random Hamilton cycle and a random (r − 2)-regular multigraph G^{∗}(n, r − 2).

Let us say that two random objects X_{n} and Y_{n}, depending on a parameter n, are contiguous if the corresponding sequences of distributions (L(X_{n})) and (L(Y_{n})) are contiguous, and denote this by X_{n} ≈ Y_{n}. (Recall that this is an asymptotic property as n → ∞.) Moreover, let us use the notations + for the union of two independent random multigraphs on the same vertex set, and H(n) for a random Hamilton cycle on n vertices. Then the discussion above may be summarized by

G^{∗}(n, r − 2) + H(n) ≈ G^{∗}(n, r),  r ≥ 4.  (3.1)

Similarly we obtain from Theorem 4 and Proposition 3, recalling that a random perfect matching is the same as G^{∗}(n, 1) = G(n, 1) and assuming n even,

G^{∗}(n, r − 1) + G(n, 1) ≈ G^{∗}(n, r),  r ≥ 3.  (3.2)

(This is essentially proved in [21], but our use of multigraphs seems to simplify both the result and the proof.)

We note also that the operation + is commutative and associative, and that it behaves well under contiguity in the following sense.

Lemma 2. Suppose that G_{n}, H_{n}, G′_{n}, H′_{n} are random multigraphs on n vertices with some distributions such that G_{n} ≈ G′_{n} and H_{n} ≈ H′_{n}. Then G_{n} + H_{n} ≈ G′_{n} + H′_{n}.

Proof. By Proposition 4(iii), the pairs (G_{n}, H_{n}) and (G′_{n}, H′_{n}) are contiguous, and the result follows by Proposition 4(ii). □

The contiguity (3.1) does not hold for r = 3 for the simple reason that neither G^{∗}(n, 1) nor H(n) can contain any loop, and thus P(G^{∗}(n, 1) + H(n) is loopless) = 1, while P(G^{∗}(n, 3) is loopless) = P(X_{1n}^{∗} = 0) → e^{−λ_{1}} = e^{−1}. Let us therefore define the random r-regular loopless multigraph G′(n, r) to be G^{∗}(n, r) conditioned on X_{1n} = 0 (i.e. no loops). This is thus intermediate between G^{∗}(n, r) and G(n, r). (As for G^{∗}(n, r), the distribution is not the uniform one: there is a weight factor k!^{−1} for every edge with multiplicity k.) By conditioning on X_{1n} = 0 in Theorem 3, arguing as in Section 1, we see that analogues of Theorems 2, 3 and 4 hold for G′(n, r) with W > 0 a.s. for every r ≥ 3. We can now argue as above and obtain

G′(n, r − 2) + H(n) ≈ G′(n, r),  r ≥ 3  (3.3)

and (for even n)

G′(n, r − 1) + G(n, 1) ≈ G′(n, r), r ≥ 3. (3.4)

Remark 12. In particular,

G′(n, 2) + G′(n, 1) ≈ G′(n, 3) ≈ H(n) + G′(n, 1)

although G′(n, 2) ≉ H(n). This shows that cancellation is not allowed and that there is no unique subtraction corresponding to +.

We can extend (3.3) and (3.4).

Theorem 10. If r, s ≥ 1, and (r, s) ≠ (1, 1) or (2, 2), then, for even n,

G′(n, r) + G′(n, s) ≈ G′(n, r + s).  (3.5)

For any r ≥ 1 we also have

G′(n, r) + H(n) ≈ G′(n, r + 2).  (3.6)

Proof. The contiguity (3.6) is just a restatement of (3.3). For (3.5), we may assume r ≥ s. The case s = 1 is (3.4). We may thus assume r ≥ s ≥ 2, and thus r ≥ 3 (because r = s = 2 is excluded). If r = 3, then (3.3) and (3.4) yield, using Lemma 2,

G′(n, 3) + G′(n, s) ≈ G′(n, 1) + H(n) + G′(n, s) ≈ G′(n, 1) + G′(n, s + 2) ≈ G′(n, s + 3)

while for larger r we use induction in r and (3.4), yielding

G′(n, r)+G′(n, s) ≈ G′(n, r−1)+G′(n, 1)+G′(n, s) ≈ G′(n, r−1)+G′(n, s+1) ≈ G′(n, r+s).

□

The contiguity (3.5) is certainly false for r = s = 1, since G(n, 1) + G(n, 1) has no odd cycles, but the case r = s = 2, which is left open by our proof, is presumably not really an exception.

Conjecture 1.

G′(n, 2) + G′(n, 2) ≈ G′(n, 4).

In fact, essentially this has recently been proved by Hania Robalewska-Szarłat [18], although her statement considers only the corresponding random simple graphs obtained by conditioning on no multiple edges.

We also conjecture a stronger version of Robinson and Wormald [21, Conjecture 1].

Conjecture 2.

H(n) + H(n) ≈ G′(n, 4).

Note that the mixed sum is no problem: G′(n, 2) + H(n) ≈ G′(n, 4) by (3.3).

We conjecture also that (3.5) holds for odd n as well, provided r and s are even. (This would follow from Conjecture 2 and (3.3) by an easy induction.)

We now turn to Theorem 5. Again we condition on there being no loops, and obtain by the argument above

G′(n, 3) ≅ G(n, 1) + G(n, 1) + G(n, 1).  (3.7)

Using (3.4) and induction, this can be extended to sums of any number (except 2) of perfect matchings. This result has also been obtained (independently) by Molloy, Robalewska-Szarłat, Robinson and Wormald [17].

Theorem 11. Let r ≠ 2. Then, for even n,

G′(n, r) ≈ G(n, 1) + ⋯ + G(n, 1) (r terms).

It follows easily from Theorems 10 and 11 that, at least for even n, any sum of 3 or more independent G′(n, r_{i}) is contiguous to G′(n, ∑ r_{i}), except possibly when every r_{i} = 2. We may here also replace some terms G′(n, 2) by H(n), and the only possible exceptions are when all terms equal G′(n, 2) or when all equal H(n).

We have worked with the loopless multigraphs G′(n, r) which were easy to handle. We conjecture that similar results hold when we allow loops.

Conjecture 3. If r, s ≥ 1 and (r, s) ≠ (1, 1), then

G^{∗}(n, r) + G^{∗}(n, s) ≈ G^{∗}(n, r + s).

Results for random regular graphs follow from the results above by conditioning on there being no multiple edges, cf. Proposition 4(i). Note, however, that the union of two graphs in general is a multigraph, so the results say, for example, that G(n, r) is contiguous to the union of r independent perfect matchings, conditioned on there being no multiple edges.

For random regular bipartite and directed graphs, we obtain some similar (but less complete) results from Theorems 6–8; we leave the details to the reader. A bipartite version of Theorem 11 has recently been proved by Hania Robalewska-Szarłat (personal communication). Note, moreover, that if the variance for Hamilton cycles in a random bipartite multigraph is as expected,

E H(B^{∗}(n, r))^{2}/(E H(B^{∗}(n, r)))^{2} → 1 for r ≥ 3,

then not only B^{∗}(n, r) ≈ B(n, r−2)+H(2n) would follow; these two models actually would be asymptotically equivalent in the stronger sense that lim_{n→∞} P_{n}(A_{n}) = lim_{n→∞} Q_{n}(A_{n}) for any events A_{n} such that one of the limits exists.

For r = 2, we have here considered the models G^{∗}(n, 2), H(n) and G(n, 1) + G(n, 1) (and conditioned versions of them). A fourth interesting model is D^{0}(n, 1), obtained by ignoring the directions of the edges in the random digraph D(n, 1), which is the same as a random permutation. (In this model, the probability of a certain 2-regular multigraph is proportional to 2^{# cycles}.) These four models are all non-contiguous, even if we condition on no loops and no multiple edges; this is easily seen by Proposition 7 and 8, letting X_{n} ∈ Z^{∞} be the vector (X_{in})_{i=3}^{∞}, since we have, for the means of the limiting Poisson variables,

λ_{i} = \{ \begin{matrix}1/2i & for G^{∗}(n, 2) \\ 0 & for H(n) \\ (1 + (−1)^{i})/2i & for G(n, 1) + G(n, 1) \\ 1/i & for D^{0}(n, 1). \end{matrix}  (3.8)

Nevertheless, we have seen that adding an independent G(n, 1) to one of the three first models (and conditioning on no multiple edges) yields three contiguous distributions; we conjecture that adding it to the fourth also gives a contiguous distribution. Similarly, we conjecture that the sum of any two of these four (different or not) is contiguous to G(n, 4) after conditioning on being simple.

Let us finally prove another contiguity result. Recall that we have defined the random multigraph G^{∗}(n, r) as obtained from a uniformly distributed configuration. The distribution of G^{∗}(n, r) is not uniform on the set of all r-regular multigraphs on n given vertices (unless r = 1), but it is contiguous to the uniform distribution.

Theorem 12. For any fixed r ≥ 1, G^{∗}(n, r) is contiguous to a random r-regular multigraph chosen with the uniform distribution.

Proof. Let P_{n} be the distribution of G^{∗}(n, r) and let Q_{n} be the uniform distribution on the set of all r-regular multigraphs on [n].

Define, for a given multigraph, Y′_{n} = 2^{X_{1n}} and Y′′_{n} = ∏_{j=2}^{r}(j!)^{m_{j}}, where X_{1n} as usual is the number of loops and m_{j} is the number of edges of multiplicity j. Let Y_{n} = Y′_{n}Y′′_{n}. It is easily seen that dP_{n}/dQ_{n} = c_{n}Y_{n}^{−1}, or dQ_{n}/dP_{n} = c_{n}^{−1}Y_{n}, where c_{n} is a normalizing constant; in fact, c_{n} = E_{P_{n}} Y_{n}. The probability that G^{∗}(n, r) has any triple edges tends to 0 as n → ∞, and thus P_{n}(Y′′_{n} ≠ 2^{X_{2n}}) → 0. Consequently, under P_{n},

Y_{n} ⟶^{d} Y = 2^{Z_{1}+Z_{2}},  (3.9)

where Z_{i} ∼ Po ((r − 1)^{i}/2i) are as usual.

We will show that the variables Y_{n} are uniformly integrable under P_{n}. This implies

c_{n} = E_{P_{n}} Y_{n} → E Y < ∞,

and thus, under P_{n},

\frac{dQ_{n}}{dP_{n}} ⟶^{d} (E Y)^{−1}Y.  (3.10)

The result then follows by Proposition 3, because Y ≥ 1 and thus (E Y)^{−1}Y > 0.

To show that Y_{n} are uniformly integrable, it suffices to show that sup_{n} E Y_{n}^{2} < ∞ (all expectations in the remainder of the proof are for P_{n}). By Hölder’s inequality it suffices to prove sup_{n} E(Y′_{n})^{4} < ∞ and sup_{n} E(Y′′_{n})^{4} < ∞. Now (Y′_{n})^{4} = 2^{4X_{1n}}. Define X̃_{n} = ∑_{j=2}^{r} m_{j}, the number of multiple edges (counted just once each). Then, crudely,

Y′′_{n} ≤ (r!)X̃_{n} and thus (Y′′_{n})^{4} ≤ (r!^{4})X̃_{n}.

Let p_{k} be the probability that a random configuration contains k given edges, 1 ≤ k ≤ rn/2. Then p_{k} = ∏_{i=1}^{k}(rn − 2i + 1)^{−1}, and thus, using Stirling’s formula,

p_{k}^{1/k} ≤ p_{rn/2}^{2/rn} = (\frac{2^{rn/2}(rn/2)!}{(rn)!})^{2/rn} ≤ \frac{e}{rn}.

There are \binom{r}{2}n ≤ r^{2}n possible edges in the configuration that will create loops. Hence

P(X_{1n} = k) ≤ \binom{r^{2}n}{k}p_{k} ≤ \frac{1}{k!}(r^{2}n)^{k}(\frac{e}{rn})^{k} = \frac{1}{k!}(er)^{k}

and

E 2^{4X_{1n}} ≤ ∑_{k=0}^{∞} \frac{1}{k!}2^{4k}(er)^{k} = exp(16er) < ∞.

Similarly, there are less than n^{2}r^{4} pairs of edges in the configuration that will create parallel edges. Hence

P(X̃_{n} = k) ≤ \frac{1}{k!}(n^{2}r^{4})^{k}p_{2k} ≤ \frac{1}{k!}(e^{2}r^{2})^{k}

and

E(Y′′_{n})^{4} ≤ E(r!^{4})X̃_{n} ≤ exp(e^{2}r^{2}r!^{4}) < ∞.

This completes the proof. □

Remark 13. By (3.10) and (3.9), under P_{n},

\frac{dQ_{n}}{dP_{n}} ⟶^{d} (E Y)^{−1}Y = e^{−λ_{1}−λ_{2}}2^{Z_{1}+Z_{2}}

and this convergence holds jointly with X_{in} ⟶^{d} Z_{i}. Proposition 5 applied to a vector of cycle counts (X_{in})_{i=1}^{m}, with m ≥ 2 fixed, yields, with λ_{i} = (r − 1)^{i}/2i,

Q_{n}(X_{1n} = x_{1}, …, X_{mn} = x_{m}) → Q_{n}(Z_{1} = x_{1}, …, Z_{m} = x_{m})

= e^{−λ_{1}−λ_{2}}2^{x_{1}+x_{2}} P(Z_{1} = x_{1}, …, Z_{m} = x_{m})

= ∏_{i=1}^{2} \frac{(2λ_{i})^{x_{i}}}{x_{i}!} e^{−2λ_{i}} ∏_{i=3}^{m} \frac{λ_{i}^{x_{i}}}{x_{i}!} e^{−λ_{i}}.

Hence, for a random r-regular multigraph with the uniform distribution, X_{in} ⟶^{d} Po(λ′_{i}), with independent limits, where

λ′_{i} = \{ \begin{matrix}(r − 1)^{i}/i, & i = 1, 2, \\ (r − 1)^{i}/2i, & i ≥ 3. \end{matrix}

4. Contiguity and asymptotic distributions

We can easily obtain results on asymptotic distributions under the various (non-uniform) distributions of random (multi-)graphs studied in Section 3.

To begin with, we observe that if P_{n} is the distribution of G(n, r) (or G′(n, r); or G^{∗}(n, r)), then under P_{n} the cycle counts X_{in} ⟶^{d} Z_{i} ∼ Po(λ_{i}), with Z_{i} independent and λ_{i} = \frac{1}{2i}(r − 1)^{i}, i ≥ 3 (or i ≥ 2; or i ≥ 1). Similarly, if Q_{n} is another of the distributions of multigraphs considered here, then under Q_{n} we have

X_{in} ⟶^{d} Z′_{i} ∼ Po(λ′_{i})  (4.1)

with Z′_{i} independent, for some λ′_{i}. This follows easily from Proposition 5, by the argument in Remark 13, in the cases when dQ_{n}/dP_{n} = Y_{n}/ E Y_{n} for a variable Y_{n} satisfying the conclusion of Theorem 1; then λ′_{i} = λ_{i}(1 + δ_{i}). This is, however, going in circles since (4.1) then really is just a reformulation of our assumption A2. We verify A2 and thus (4.1) for several cases in Section 5. Other cases follow similarly; for example, if Q_{n} is the distribution of G^{∗}(n, r_{1}) + G^{∗}(n, r_{2}), r_{1} + r_{2} = r, then it is easy to show that (4.1) holds with

λ′_{i} = \frac{1}{2i} Tr ( \begin{matrix}r_{1} − 1 & r_{1} \\ r_{2} & r_{2} − 1 \end{matrix} )^{i} = λ_{i}(1 + (−\frac{1}{r − 1})^{i}).

We write λ′_{i} = λ_{i}(1 + δ′_{i}) and observe that in all examples, δ′_{i} are rather small perturbations. This, in fact, is necessary if P_{n} and Q_{n} are contiguous, since Propositions 7 and 8 then implies ∑ λ_{i} min(δ′_{i}, (δ′_{i})^{2}) < ∞. In all cases we consider, sup δ′_{i} < ∞ and we simply have

∑_{i} λ_{i}(δ′_{i})^{2} < ∞.  (4.2)

Now assume that Y_{n} is a functional of the random regular (multi-)graph, such that under P_{n}, for some δ_{i} ≥ −1,

Y_{n}/ E_{P_{n}} Y_{n} ⟶^{d} ∏_{i}(1 + δ_{i})^{Z_{i}}e^{−λ_{i}δ_{i}}  (4.3)

jointly with X_{in} ⟶^{d} Z_{i}; for example, Y_{n} may be one of the variables studied in Theorems 2–5. Then Proposition 6 applied to Y_{n}/ E_{P_{n}} Y_{n}, with X_{n} = (X_{in})_{i} ∈ S = R^{∞} and f(x) = ∏_{i}(1 + δ_{i})^{x_{i}}e^{−λ_{i}δ_{i}} (defined to be 0, for example, when the product diverges), yields that under Q_{n},

Y_{n}/ E_{P_{n}} Y_{n} ⟶^{d} ∏_{i}(1 + δ_{i})^{Z′_{i}}e^{−λ_{i}δ_{i}}.  (4.4)

We thus obtain the asymptotic distribution of Y_{n} under Q_{n}, with a suitable normalization, by changing the means of the Poisson variables in (4.3). If we define

a_{n} = exp(∑_{i} λ_{i}δ_{i}δ′_{i}) E_{P_{n}} Y_{n},

then (4.4) may be rewritten as (under Q_{n})

Y_{n}/a_{n} ⟶^{d} ∏_{i}(1 + δ_{i})^{Z′_{i}}e^{−λ′_{i}δ_{i}}.  (4.5)

Here the right hand side has mean 1. If furthermore a_{n} ∼ E_{Q_{n}} Y_{n}, we may here replace a_{n} by E_{Q_{n}} Y_{n} in complete analogy with (4.3). For example, we may do this if both Y_{n}/ E_{P_{n}} Y_{n} and dQ_{n}/dP_{n} are uniformly square integrable for P_{n}, because it is easily shown that then Y_{n}/a_{n} is uniformly integrable under Q_{n}, and thus E_{Q_{n}}(Y_{n}/a_{n}) → 1.

We can now write down various asymptotic distributions for the variables and models of random regular graphs studied above; we leave the details to the reader.

5. Proofs of Theorem 1 and Lemma 1.

Proof of Theorem 1. We begin by observing that, since Z_{i} ∼ Po(λ_{i}), E(1 + δ_{i})^{Z_{i}} = e^{λ_{i}(1+δ_{i})−λ_{i}} = e^{λ_{i}δ_{i}} and E((1 + δ_{i})^{Z_{i}})^{2} = e^{λ_{i}(1+δ_{i})^{2}−λ_{i}} = e^{λ_{i}(2δ_{i}+δ_{i}^{2})}. Thus, defining

W^{(m)} = ∏_{1}^{m}(1 + δ_{i})^{Z_{i}}e^{−λ_{i}δ_{i}},

W^{(m)} is a product of independent variables with mean 1, and

E(W^{(m)})^{2} = ∏_{1}^{m} e^{λ_{i}δ_{i}^{2}} = exp(∑_{1}^{m} λ_{i}δ_{i}^{2}) → exp(∑_{1}^{∞} λ_{i}δ_{i}^{2}) < ∞ as m → ∞.

Hence the sequence (W^{(m)})_{m=1}^{∞} is an L^{2}-bounded martingale and thus the limit W = lim_{m→∞} W^{(m)} exists a.s. and in L^{2}, with E W^{2} = exp(∑_{1}^{∞} λ_{i}δ_{i}^{2}). We observe for future use that

E |W − W^{(m)}|^{2} = E W^{2} − E(W^{m})^{2} = exp(∑_{1}^{∞} λ_{i}δ_{i}^{2}) − exp(∑_{1}^{m} λ_{i}δ_{i}^{2}).  (5.1)

In order to show that W ≠ 0 a.s., except when Z_{i} > 0 for some i with δ_{i} = −1, let us break the product defining W into two parts W_{1} = ∏_{δ_{i}<−1/2} and W_{2} = ∏_{δ_{i}≥−1/2}. For W_{1} we observe that although there may conceivably be infinitely many indices in I_{1} = {i : δ_{i} < −1/2}, condition A3 implies that E ∑_{I_{1}} Z_{i} = ∑_{I_{1}} λ_{i} ≤ 4 ∑_{I_{1}} λ_{i}δ_{i}^{2} < ∞, and similarly ∑_{I_{1}} |λ_{i}δ_{i}| < ∞. Hence there are a.s. only finitely many non-zero Z_{i}, i ∈ I_{1}, and W = e^{− ∑_{I_{1}} λ_{i}δ_{i}} ∏_{I_{1}}(1 + δ_{i})^{Z_{i}}, where the product really is a finite product which is positive unless some factor vanishes, i.e. unless Z_{i} > 0 for some i with δ_{i} = −1.

For W_{2} we define δ̃_{i} = −δ_{i}/(1+δ_{i}), i ∈ I_{2} = \{i : δ_{i} ≥ −\frac{1}{2}\}, and note that ∑_{I_{2}} λ_{i}δ̃_{i}^{2} < ∞ and thus the argument above shows that

W̃_{2} = ∏_{I_{2}}(1 + δ̃_{i})^{Z_{i}}e^{−λ_{i}δ̃_{i}}

converges a.s. with W̃_{2} < ∞. However, since (1 + δ_{i})(1 + δ̃_{i}) = 1,

W_{2}W̃_{2} = ∏_{I_{2}} e^{−λ_{i}(δ_{i}+δ̃_{i})} = exp(− ∑_{I_{2}} λ_{i}δ_{i}^{2}/(1 + δ_{i})) > 0,

so W_{2} > 0 a.s., which completes the proof that W > 0 a.s. except when some factor vanishes.

For the rest of the proof we make, without loss of generality, two simplifying assumptions. First we may assume E Y_{n} = 1. Secondly, we invoke a theorem by Skorokhod [23] which implies that although the variables X_{in} and Y_{n} originally may be defined on different probability spaces for different n, and Z_{i} on yet another probability space, we may replace them by other variables having the same distributions, such that they become defined on a single probability space and the convergence in A1 holds a.s., i.e. X_{in} → Z_{i} a.s. as n → ∞ for each i.

Fix a large integer m and define the functions

f_{n}(x_{1}, …, x_{m}) = E(Y_{n} | X_{1n} = x_{1}, …, X_{mn} = x_{m})
f_{∞}(x_{1}, …, x_{m}) = lim_{n→∞} f_{n}(x_{1}, …, x_{m}) = ∏_{1}^{m}(1 + δ_{i})^{x_{i}}e^{−λ_{i}δ_{i}},

where we used assumption A2, and the random variable

Y_{n}^{(m)} = E(Y_{n} | X_{1n}, …, X_{mn}) = f_{n}(X_{1n}, …, X_{mn}).

Then E(Y_{n}^{(m)})^{2} = ∑_{x_{1},...,x_{m}} P(X_{1n} = x_{1}, …, X_{mn} = x_{m})f_{n}(x_{1}, …, x_{m})^{2} and thus, by Fatou’s lemma and assumptions A1 and A2,

lim inf_{n→∞} E(Y_{n}^{(m)})^{2} ≥ ∑_{x_{1},...,x_{m}} lim_{n→∞} P(X_{1n} = x_{1}, …, X_{mn} = x_{m})f_{n}(x_{1}, …, x_{m})^{2}

= ∑_{x_{1},...,x_{m}} P(Z_{1} = x_{1}, …, Z_{m} = x_{m})f_{∞}(x_{1}, …, x_{m})^{2}

= E f_{∞}(Z_{1}, …, Z_{m})^{2} = E(W^{(m)})^{2} = exp(∑_{1}^{m} λ_{i}δ_{i}^{2}).

Consequently, since Y_{n}^{(m)} is a conditional expectation of Y_{n},

lim sup_{n→∞} E |Y_{n} − Y_{n}^{(m)}|^{2} = lim sup_{n→∞}(E Y_{n}^{2} − E(Y_{n}^{(m)})^{2})
≤ exp(∑_{1}^{∞} λ_{i}δ_{i}^{2}) − exp(∑_{1}^{m} λ_{i}δ_{i}^{2}).  (5.2)

Furthermore, by our simplifying assumption X_{in} → Z_{i} a.s., we have a.s., for all large n, X_{in} = Z_{i}, i ≤ m, and thus

lim_{n→∞} Y_{n}^{(m)} = lim_{n→∞} f_{n}(Z_{1}, …, Z_{m}) = f_{∞}(Z_{1}, …, Z_{m}) = W^{(m)}  a.s.  (5.3)

Finally using Chebyshev’s inequality, (5.3), (5.2) and (5.1), we obtain for every ε > 0,

lim sup_{n→∞} P(| Y_{n} − W |> 3ε)

≤ lim sup_{n→∞} P(| Y_{n} − Y_{n}^{(m)} |> ε) + lim sup_{n→∞} P(| Y_{n}^{(m)} − W^{(m)} |> ε) + P(| W^{(m)} − W |> ε)

≤ ε^{−2} lim sup_{n→∞} E | Y_{n} − Y_{n}^{(m)} |^{2} +0 + ε^{−2} E | W − W^{(m)} |^{2}

≤ 2ε^{−2}[exp(∑_{1}^{∞} λ_{i}δ_{i}^{2}) − exp(∑_{1}^{m} λ_{i}δ_{i}^{2})].  (5.4)

We now let m → ∞, keeping ε fixed. The right hand side of (5.4) tends to 0, so the left hand side, which does not depend on m, has to vanish for each ε > 0, which proves Y_{n} ⟶^{p} W, and completes the proof of the theorem. □

Proof of Lemma 1. Define a new probability measure Q_{n} by Q_{n}(A) = E(Y_{n}I_{A})/ E Y_{n} for every event A in the probability space Ω_{n} where X_{in} and Y_{n} are defined. Then the assumption may be written

E_{Q_{n}}((X_{in})_{j_{1}} ⋯ (X_{mn})_{j_{n}}) → ∏_{1}^{m} μ_{i}^{j_{i}},  (5.5)

and the method of moments yields that under the measures Q_{n},

X_{in} ⟶^{d} Po(μ_{i}),

jointly for all i with independent limits. This and A1 yield, for any x_{1}, …, x_{m},

\frac{E(Y_{n} | X_{1n} = x_{1}, …, X_{mn} = x_{m})}{E Y_{n}} = \frac{E(Y_{n}I(X_{1n} = x_{1}, …, X_{mn} = x_{n}))}{E Y_{n} P(X_{1n} = x_{1}, …, X_{mn} = x_{n})}

= \frac{Q_{n}(X_{1n} = x_{1}, …, X_{mn} = x_{m})}{P(X_{1n} = X_{1}, …, X_{mn} = x_{m})}

→ \frac{∏_{i=1}^{m} μ_{i}^{x_{i}}e^{−μ_{i}}/x_{i}!}{∏_{i=1}^{m} λ_{i}^{x_{i}}e^{−λ_{i}}/x_{i}!} = ∏_{i=1}^{m}(\frac{μ_{i}}{λ_{i}} )^{x_{i}}e^{λ_{i}−μ_{i}}

which is A2 with μ_{i} = λ_{i}(1 + δ_{i}). □

6. Proofs of Theorems 2–9

We finally show how Theorems 2–9 follow from Theorem 1. We let Y_{n} be the studied variable and X_{in} the number of cycles of length i in the random structure. (For the directed case, we use X_{Cn} as in Section 1.)

The numbers λ_{i} are determined such that A1 holds and then δ_{i} are given by A2, see also Remark 5. We will in all cases show A2 by Lemma 1; this usually requires long but rather straight forward combinatorial calculations. It then remains (besides A3) to verify the variance estimate A4, and that is often the most difficult part of the proof. Fortunately, we can usually just quote the needed result from work by others.

Proof of Theorem 2 and 3. Most steps are the same for the random graphs and multigraphs, so we do both theorems together. We let in the proof i ≥ 1 in the multigraph case but i ≥ 3 in the graph case.

A1, with λ_{i} = \frac{1}{2i}(r − 1)^{i}, is a result by Bollobás [4], [5] and Wormald [24].

For A2 we use Lemma 1 and have to compute factorial moments. This is done in [20] (at least for G(n, 3)), using generating functions to keep track of the different possibilities for intersections of cycles.

We will here give a slightly different argument, using matrices, which will be easy to adapt to other situations.

We will for simplicity only verify

\frac{E H_{n}^{∗}X_{kn}}{E H_{n}^{∗}} → μ_{k}  as n → ∞;  (6.1)

the extension to mixed higher factorial moments is routine. We restrict ourselves for the time being to random multigraphs, which (sometimes) are easier to handle than graphs.

Let V be the vertex set of G^{∗}(n, r) and Ṽ = V ×[r] the set of half-edges, and let K(Ṽ) be the complete graph on Ṽ. Let G̃ denote the random configuration which defines G^{∗}(n, r). For any subgraph A of K(Ṽ), denote its projection by A^{0}; in particular, G̃^{0} = G^{∗}(n, r).

Let C̃_{k} be the family of all sets of k edges in K(Ṽ) that project to a k-cycle. Then, using the symmetry,

\frac{E X_{kn}H_{n}^{∗}}{E H_{n}^{∗}} = \frac{∑_{C̃∈C̃_{k}} ∑_{D̃∈C̃_{n}} P(C̃, D̃ ⊂ G̃)}{∑_{D̃∈C̃_{n}} P(D̃ ⊂ G̃)} = ∑_{C̃∈C̃_{k}} ∑_{D̃∈C̃_{n}} \frac{1}{|C̃_{n}|} P(C̃ ⊂ G̃ | D̃ ⊂ G̃). (6.2)

We compute this sum as follows. We assume n > k + 1. We first partition the sum according to the projection C of C̃, which may be any of the \frac{1}{2k} (n)_{k} ∼ \frac{1}{2k} n^{k} different kcycles on V. (For k = 1 or 2, there are slight modifications, which we omit; the final result is the same.) We then further partition the sum according to the graph B = (C̃∩D̃)^{0} ⊂ C. It is easily seen that the case B = C cannot occur, since it would imply C̃ ⊂ D̃. Now consider one of the remaining 2^{k} − 1 choices of B; B consists of j ≥ 0 paths in C. Let us traverse C in an arbitrary direction and partition the set of vertices of C into the four sets V_{00}, V_{01}, V_{10}, V_{11} where V_{00} consists of the vertices not adjacent to an edge in B, V_{01} consists of the vertices followed but not preceded by an edge in B, and similarly V_{10} and V_{11} consist of the vertices preceded and not followed, or followed, respectively, by an edge in B. We define m_{00} = |V_{00}|, m_{01} = |V_{01}|, m_{10} = |V_{10}| and m_{11} = |V_{11}|; note that m_{01} = m_{10} = j and that the number of edges in B is m_{01} + m_{11}. The Hamilton cycle D = D̃^{0} has to contain B; these Hamilton cycles in K_{n} may be constructed by selecting a Hamilton cycle on the set of n − m_{11} − m_{10} points obtained by contracting every path in B to a point, and furthermore selecting an orientation for each of these m_{01} paths. Hence there are 2^{m_{01}} \frac{1}{2}(n − m_{11} − m_{10} − 1)! ∼ 2^{m_{01}}n^{−m_{11}−m_{10}}|C_{n}| choices of D, given C and B, and thus ∼ 2^{m_{01}}n^{−m_{11}−m_{10}}|C̃_{n}| choices of D̃.

It remains to choose C̃. For C, B and D̃ as above, the edges in C̃ ∩ D̃ are already determined; to determine the others, we have to make a choice among r − 2 possibilities at each vertex in V_{01} ∪ V_{10} (remembering that 2 of the r original possibilities are used by D̃), and a choice among (r − 2)(r − 3) possibilities at each vertex in V_{00}. Hence there are (r − 2)^{m_{01}+m_{10}+m_{00}}(r − 3)^{m_{00}} choices of C̃. For each of these,

P(C̃ ⊂ G̃ | D̃ ⊂ G̃) = \frac{1}{(rn − 2n − 1) ⋯ (rn − 2n − 2(m_{00} + m_{01}) + 1)}
∼ ((r − 2)n)^{−m_{00}−m_{01}}.

We thus see that the contribution to (6.2) for a given C and B ≠ C is

∼ 2^{m_{01}}n^{−m_{11}−m_{10}}(r − 2)^{m_{01}+m_{10}+m_{00}}(r − 3)^{m_{00}}((r − 2)n)^{−m_{00}−m_{01}}
= 2^{m_{01}}(r − 2)^{m_{10}}(r − 3)^{m_{00}}n^{−k}.  (6.3)

By symmetry, all \frac{1}{2k} (n)_{k} choices of C give the same contribution, so we may fix one of them and obtain (also for k = 1, 2)

\frac{E X_{kn}H_{n}^{∗}}{E H_{n}^{∗}} ∼ \frac{1}{2k} ∑_{B≠C}(r − 3)^{m_{00}}2^{m_{01}}(r − 2)^{m_{10}}

= \frac{1}{2k} ( ∑_{B⊆C}(r − 3)^{m_{00}}2^{m_{01}}(r − 2)^{m_{10}} − 1).

Number the edges in C e_{1}, …, e_{k} (in order). The last sum is over the 2^{k} full subgraphs B ⊆ C; using the indicators I(e_{i} ∈ B) we may rewrite it as a sum over the sequences in {0, 1}^{k}, and it is then seen that the sum equals Tr(A^{k}), where A is the matrix

A = ( \begin{matrix}r − 3 & 2 \\ r − 2 & 1 \end{matrix} ) .  (6.4)

We have thus proved (6.1) with

μ_{k} = \frac{1}{2k} (Tr(A^{k}) − 1).  (6.5)

However, A has the eigenvalues r − 1 and −1, and thus Tr(A^{k}) = (r − 1)^{k} + (−1)^{k}. We finally obtain (6.1) and A2′ with

μ_{k} = \frac{1}{2k} ((r − 1)^{k} + (−1)^{k} − 1) = λ_{k}(1 + \frac{(−1)^{k} − 1}{(r − 1)^{k}}).  (6.6)

Lemma 1 now shows that A2 holds with

δ_{k} = \frac{(−1)^{k} − 1}{(r − 1)^{k}} = \{ \begin{matrix}−2/(r − 1)^{k} & k odd, \\ 0 & k even. \end{matrix}  (6.7)

(It is the fact that δ_{k} vanishes for even k that makes the number of Hamilton cycles asymptotically independent of the even cycle counts. The calculation above may shed some light on this phenomenon, but it still seems surprising.)

Having verified A2 for the multigraph case, we note that the graph case follows immediately by specializing to x_{1} = x_{2} = 0, using in particular

\frac{E H_{n}}{E H_{n}^{∗}} = \frac{E(H_{n}^{∗} | X_{1n} = X_{2n} = 0)}{E H_{n}^{∗}} → e^{−λ_{1}δ_{1}−λ_{2}δ_{2}} = e,  (6.8)

which we obtained in a different way in Section 1.

The values of λ_{i} and δ_{i} yield

∑_{1}^{∞} λ_{i}δ_{i}^{2} = ∑_{i odd} \frac{2}{i}(r − 1)^{−i} = log(1 + \frac{1}{r − 1}) − log(1 − \frac{1}{r − 1})
= log \frac{r}{r − 2},  (6.9)

and thus (for the graph case) ∑_{3}^{∞} λ_{i}δ_{i}^{2} = log \frac{r}{r−2} − \frac{2}{r−1}. Hence A3 holds, and the variance condition A4 says

E H_{n}^{2}/(E H_{n})^{2} → \frac{r}{r − 2}e^{−2/(r−1)}  (6.10)

in the graph case, and

E H_{n}^{∗2}/(E H_{n}^{∗})^{2} → \frac{r}{r − 2}.  (6.11)

For r = 3, (6.10) is proved in [19]. Robinson and Wormald use this case in [20] and they state the result for r ≥ 4 (when the proof is much more difficult) in [21]. The multigraph case (6.11) has been verified by Frieze, Jerrum and Molloy [9].

This completes the verification of the conditions in Theorem 2 for these two cases. □

Remark 14. In fact, (6.11) implies (6.10) by the results of Section 1, see (1.11).

Proof of Theorem 4. We argue as in the preceding proof, but now assume that D̃ projects to a perfect matching on V. Hence B consists of paths of length 1 only, which we account for by a factor 0^{m_{11}}. (The case B = C is no longer special.) Moreover, no factor 2^{m_{01}} appears and D̃ uses only one vertex for each vertex in V so r − 2 and r − 3 have to be replaced by r − 1 and r − 2. Hence we now take

A = ( \begin{matrix}r − 2 & 1 \\ r − 1 & 0 \end{matrix} )  (6.12)

and obtain (6.1) and A2′ with

μ_{k} = \frac{1}{2k} Tr(A^{k}) = \frac{1}{2k} ((r − 1)^{k} + (−1)^{k}) = λ_{k} (1 + (−\frac{1}{r − 1})^{k}) ,  (6.13)

since A has the eigenvalues r − 1 and −1, and λ_{k} is as above.

This yields A2 with

δ_{k} = \frac{(−1)^{k}}{(r − 1)^{k}} ,  k ≥ 1,  (6.14)

and

∑_{1}^{∞} λ_{k}δ_{k}^{2} = ∑_{1}^{∞} \frac{1}{2k} (\frac{1}{r − 1})^{k} = −\frac{1}{2} log (1 − \frac{1}{r − 1}) = \frac{1}{2} log \frac{r − 1}{r − 2}.  (6.15)

Hence A4 says

E M_{n}^{∗2}/(E M_{n}^{∗})^{2} → \sqrt{\frac{r − 1}{r − 2}};  (6.16)

for graphs we similarly need

E M_{n}^{2}/(E M_{n})^{2} → \sqrt{\frac{r − 1}{r − 2}} exp (−\frac{1}{2(r − 1)} − \frac{1}{4(r − 1)^{2}} ) .  (6.17)

This has been proved by Bollobás and McKay [6] (at least (6.17); (6.16) is similar), which completes the proof. □

Proof of Theorem 5. Although we only have been able to complete the proof for r = 3, we do as much as possible for a general r ≥ 3 in order to show clearly what is missing in the general case. It suffices to prove the multigraph case; the graph case follows by conditioning as in Section 1.

The probability measure Q_{n}(A) = E(U_{n}^{∗}I_{A})/ E U_{n}^{∗} is the distribution of the random multigraph obtained as the union of r independent random perfect matchings, cf. Section 3. It is easily seen that if C is any of the ∼ n^{i}/2i cycles of length i in the complete graph, then C appears in this union with probability ∼ N(i, r)n^{−i}, where N(i, r) is the number of r-colourings of the edges in C such that no two adjacent edges have the same colour. Hence we obtain

E(U_{n}^{∗}X_{in})/ E U_{n}^{∗} = E_{Q_{n}}(X_{in}) → \frac{1}{2i}N(i, r)

and, more generally by the same argument, A2′ with μ_{i} = \frac{1}{2i}N(i, r). Hence A2 holds by Lemma 1. Furthermore, N(i, r) = Tr A^{i}, where A is the r × r-matrix (1 − δ_{ij})_{i,j=1}^{r}. Since A has eigenvalues r − 1 and −1, the latter with multiplicity r − 1, N(i, r) = (r − 1)^{i} + (r − 1)(−1)^{i} and

δ_{i} = μ_{i}/λ_{i} − 1 = N(i, r)/(r − 1)^{i} − 1 = (−1)^{i}(r − 1)^{1−i}.  (6.18)

This gives

∑_{1}^{∞} λ_{i}δ_{i}^{2} = ∑_{1}^{∞} \frac{1}{2i}(r − 1)^{2−i} = −\frac{(r − 1)^{2}}{2} log (1 − \frac{1}{r − 1})

= \frac{(r − 1)^{2}}{2} log \frac{r − 1}{r − 2},  (6.19)

which verifies A3 and shows that A4 is equivalent to

\frac{E(U_{n}^{∗})^{2}}{(E U_{n}^{∗})^{2}} → (\frac{r − 1}{r − 2})^{(r−1)^{2}/2}  (6.20)

The result now follows by the following moment estimates. □

Lemma 3. Let be as above. For any r ≥ 1, as n → ∞,

E U_{n}^{∗} ∼ 2^{(r−1)/2} (\frac{r!}{r^{r/2}} )^{n} .

If r = 3, then furthermore

\frac{E(U_{n}^{∗})^{2}}{(E U_{n}^{∗})^{2}} → (\frac{r − 1}{r − 2})^{(r−1)^{2}/2} = 4.

The proof of Lemma 3 is rather long, and we postpone it to the next section.

Proof of Theorem 6. We argue as for Theorem 4 and obtain, with A given by (6.12), (6.1) and A2′ with

μ_{k} = \frac{1}{k} Tr A^{k} = λ_{k} (1 + (−\frac{1}{r − 1})^{k}) ,  k even,  (6.21)

and thus A2 holds with

δ_{k} = (r − 1)^{−k},  k even.  (6.22)

Hence

∑_{i} λ_{i}δ_{i}^{2} = ∑_{j=1}^{∞} \frac{1}{2j} (r − 1)^{−2j} = −\frac{1}{2} log (1 − (r − 1)^{−2}) = \frac{1}{2} log \frac{(r − 1)^{2}}{(r(r − 2))}

and A4 follows by (1.18), which was proved by Bollobás and McKay [6] (they state the corresponding result for B(n, r), but the argument is the same). □

Proof of Theorem 7. We argue as for Theorem 3 in order to estimate E(H_{n}X_{Cn})/ E H_{n} for an oriented cycle C of length k.

Let W be the vertex set of C, let d_{c}(v) denote the out-degree in C of a vertex v ∈ W, and partition W into W′ = {v ∈ W : d_{C}(v) = 1} and W′′ = {v ∈ W : d_{C}(v) = 0 or 2}. Let also V′_{ij} = W′ ∩ V_{ij}, V′′_{ij} = W′′ ∩ V_{ij}, m′_{ij} = |V′_{ij}| and m′′_{ij} = |V′′_{ij}|. If m′′_{11} > 0, i.e. if there is an interior vertex in B with out-degree or in-degree 2, then no D̃ exists; we account for that by a factor 0^{m′′_{11}}. Moreover, there is no factor 2^{m_{01}} and when choosing C̃ we now have r − 1 choices at each vertex in V_{01} ∪ V_{10}, (r − 1)(r − 2) at each vertex in V′′_{00} and (r − 1)^{2} at each vertex in V′_{00}; furthermore, P(C̃ ⊂ G̃ | D̃ ⊂ G̃) ∼ ((r − 1)n)^{−m_{00}−m_{01}}.

The total contribution for a given C and B ≠ C is thus, cf. (6.3),

∼ n^{−k}0^{m′′_{11}}(r − 1)^{m_{10}+m′_{00}}(r − 2)^{m′_{00}}

and

E(H_{n}X_{C_{n}})/ E H_{n} → μ_{C} = \frac{1}{aut(C)} ∑_{B≠C} 0^{m′′_{11}}(r − 1)^{m_{10}+m′_{00}}(r − 2)^{m′′_{00}}.  (6.23)

We calculate this sum by adding and subtracting the term with B = C, which vanishes except when C is directed; it then equals 1. Let the vertices of C be v_{i}, i = 1, …, k, in order (starting from an arbitrary vertex in any direction). The full sum for all B ⊆ C equals

Tr(∏_{i}^{k} A_{i}), with A_{i} = A′ = ( \begin{matrix}r − 1 & 1 \\ r − 1 & 1 \end{matrix} ) when v_{i} ∈ W′ and A_{i} = A′′ = ( \begin{matrix}r − 2 & 1 \\ r − 1 & 0 \end{matrix} )

when v_{i} ∈ W′′.

These matrices commute (in fact, A′ = A′′ + I), so they have common eigenvectors. A′ has eigenvalues r and 0, and A′′ has r − 1 and −1. Thus

Tr(∏_{1}^{k} A_{i}) = r^{|W′|}(r − 1)^{|W′′|} + 0^{|W′|}(−1)^{|W′′|},

and, since C is directed exactly when W′′ = ∅, we obtain (6.1) and A2′ with

μ_{C} = \frac{1}{aut(C)} (r^{|W′|}(r − 1)^{|W′′|} + 0^{|W′|}(−1)^{|W′′|} − 0^{|W′′|}) .  (6.24)

Comparing this with (1.19), we see that there are three cases:

(i) If W′′ = ∅, then C = C_{k}, μ_{C_{k}} = \frac{1}{k} (r^{k} − 1) and

δ_{C_{k}} = −1/r^{k}.  (6.25)

(ii) If W′ = ∅, then C = C_{k}^{a} (k has to be even), μ_{C_{k}} = \frac{1}{k} ((r − 1)^{k} + 1) and

δ_{C_{k}^{a}} = 1/(r − 1)^{k}.  (6.26)

(iii) In all other cases, μ_{C} = \frac{1}{aut(C)}r^{|W′|}(r − 1)^{|W′′|} = λ_{C} and δ_{C} = 0.

Lemma 1 yields A2 as usual.

∑ λ_{C}δ_{C}^{2} = ∑_{i=1}^{∞} λ_{C_{i}}δ_{C_{i}}^{2} + ∑_{j=1}^{∞} λ_{C_{2j}^{a}}δ_{C_{2j}}^{2} = ∑_{1}^{∞} \frac{1}{i}r^{−i} + ∑_{1}^{∞} \frac{1}{2j} (r − 1)^{−2j}

= − log \frac{r − 1}{r} − \frac{1}{2} log \frac{r(r − 2)}{(r − 1)^{2}} = \frac{1}{2} log \frac{r}{r − 2}.  (6.27)

Hence A4 reads

E H_{n}^{2}/(E H_{n})^{2} → \sqrt{\frac{r}{r − 2}}.  (6.28)

This can be verified by standard arguments, using the same method as for G(n, 3). (For r > 3, the calculations for Hamilton cycles in D(n, r) thus are much simpler than for G(n, r).) We omit the details. □

Proof of Theorem 8. We can either refer to Theorem 6 and the correspondence described in Section 1, or argue as for Theorem 7; the only difference is that now we allow B = C, and thus

μ_{C} = \frac{1}{aut(C)} (r^{|W′|}(r − 1)^{|W′′|} + 0^{|W′|}(−1)^{|W′′|}) ,

which gives

δ_{C_{k}^{a}} = (r − 1)^{−k}  (6.29)

and δ_{C} = 0 for all other C. □

Proof of Theorem 9. Consider the configuration model defined by Cooper, Frieze, Molloy and Reed [8]. Take a random configuration, let Y_{n} be the number of perfect matchings and let X_{in} be the number of cycles of length i, see [8] for definitions. It is proved in [8] that A3 holds with

λ_{k} = \frac{((s − 1)(r − 1))^{k}}{2k} ,  k ≥ 1;  (6.30)

that A2′ holds with μ_{k} = λ_{k} (1 + (−1)^{k}/(r − 1)^{k}), which by Lemma 1 implies A2 with δ_{k} = (−1)^{k}/(r − 1)^{k}; and that

\frac{E Y_{n}^{2}}{(E Y_{n})^{2}} → \sqrt{\frac{r − 1}{r − s}},

which gives A4 because

∑_{1}^{∞} λ_{i}δ_{i}^{2} = ∑_{1}^{∞} \frac{1}{2i} (\frac{s − 1}{r − 1})^{i} = −\frac{1}{2} log \frac{r − s}{r − 1}.

The result follows by Theorem 1 and conditioning on X_{1n} = 0. □

7. Proof of Lemma 3

In order to avoid possible confusion over multiple edges, we work with configurations. We observe that if a multigraph G^{∗} is defined by a configuration G̃, then U(G^{∗}) is the number of r-colourings of the edges of G̃ such that each colour class projects to a perfect matching; we call such colourings proper. We write for simplicity U = U(G^{∗}(n, r)) = U_{n}^{∗}.

Let C be the set of all configurations and let us before V be the vertex set of G^{∗}(n, r) and Ṽ the set of half-edges. Then

E U = \frac{1}{|C|} ∑_{G̃∈C} |\{ proper colourings of G̃\}|

= \frac{1}{|C|}|\{ properly coloured configurations \}|.

However, any properly coloured configuration may be constructed by choosing a sequence M_{1}, …, M_{r} of (not necessarily distinct) perfect matchings on V, which are to be the projections of the colour classes, and then lifting these to a configuration by assigning endpoints in Ṽ for every edge in the matchings. There are (n−1)!! = n!/2^{n/2}(n/2)! perfect matchings, and every sequence M_{1}, …, M_{r} may be lifted in (r!)^{n} ways, corresponding to selections of one of the r! possible orderings of the edges at each vertex in V. Hence,

E U = \frac{(n − 1)!!^{r}}{(rn − 1)!!}(r!)^{n} ∼ 2^{(r−1)/2} (\frac{r!}{r^{r/2}} )^{n} ,  r ≥ 1,  (7.1)

where we use the asymptotic formula

(n − 1)!! = \frac{n!}{2^{n/2}(n/2)!} ∼ \sqrt{2} (\frac{n}{e})^{n/2} , n even.

For E U^{2} we argue similarly. We define a (proper) double colouring of a configuration to be a pair of proper colourings and obtain

E U^{2} = \frac{1}{|C|} ∑ ; G̃ |\{proper colourings of G̃\}|^{2}

= \frac{1}{|C|}|\{doubly coloured configurations\}|.

For any doubly coloured configuration, we define r^{2} partial matchings M_{ij} on V by taking for every (i, j) ∈ {1, …, r}^{2} the projection of the edges coloured i in the first colouring and j in the second. Let V_{ij} be the vertex set of M_{ij}. These sets satisfy the property that if v ∈ V and i, j ∈ {1, …, r} are given, then v ∈ M_{ik} for exactly one k and v ∈ M_{lj} for exactly one l. Conversely, any such set of r^{2} matchings comes from exactly (r!)^{n} doubly coloured configurations.

We count the number of such sets of matchings as follows. Given the matchings M_{ij} in sets V_{ij} as above, let, for each permutation σ of {1, …, r}, V_{σ} = ⋂_{i} V_{iσ(i)}, i.e. V_{σ} is the set of all vertices in V that are endpoints of edges in the matchings M_{iσ(i)}, i = 1, …, r. Then (V_{σ})_{σ∈S_{r}} is a partition of V. Conversely, given any partition (V_{σ})_{σ} of V such that the sets V_{ij} = ⋃_{σ:σ(i)=j} V_{σ} have even cardinality, we may choose M_{ij} as arbitrary perfect matchings in V_{ij}.

If we let x_{σ} = |V_{σ}|/n and

y_{ij} = |V_{ij}|/n = ∑_{σ:σ(i)=j} x_{σ},  (7.2)

then there are for given (x_{σ})_{σ∈S_{r}}, n!/ ∏_{σ}(x_{σ}n)! ways to choose (V_{σ})_{σ}, and for each of these we may choose M_{ij} in (y_{ij}n − 1)!! ways.

Summing up we have,

E U^{2} = ∑_{x} \frac{1}{(rn − 1)!!}(r!)^{n} \frac{n!}{∏_{σ}(x_{σ}n)!} ∏_{ij}(y_{ij}n − 1)!!  (7.3)

where we sum over all x = (x_{σ}) such that x_{σ} ≥ 0, ∑ x_{σ} = 1, x_{σ}n are integers and y_{ij}n are even, with y_{ij} defined by (7.2). Note that ∑_{j} y_{ij} = ∑_{σ} x_{σ} = 1 for every i, and thus ∑_{ij} y_{ij} = r.

We now proceed by standard arguments. We use Stirling’s formula and obtain, for simplicity ignoring the small modification needed when some x_{σ} = 0,

E U^{2} = ∑_{x} 2^{−1/2} (\frac{rn}{e})^{−rn/2} (r!)^{n}(2πn)^{(1−r!)/2} ∏_{σ} x_{σ}^{−1/2−x_{σ}n}2^{r^{2}/2} ∏_{ij} (\frac{y_{ij}n}{e})^{y_{ij}n/2}

·(1 + O(max_{σ}(x_{σ}n)^{−1}))

= ∑_{x} 2^{(r^{2}−1)/2}(2πn)^{(1−r!)/2} ∏_{σ} x_{σ}^{−1/2} (\frac{r!}{r^{r/2}} e^{f(x)})^{n} (1 + O(max_{σ}(x_{σ}n)^{−1})) (7.4)

where

f(x) = − ∑_{σ} x_{σ} log x_{σ} + ∑_{i,j} \frac{1}{2}y_{ij} log y_{ij}.

As is well-known, the asymptotic behaviour of such a sum depends only on the behaviour of f near its maxima.

Define x^{∗} = (x_{σ}^{∗}), with every x_{σ}^{∗} = 1/r!. The corresponding y_{ij} are all 1/r, and thus

f(x^{∗}) = − log \frac{1}{r!} + \frac{r}{2} log \frac{1}{r} = log r! − \frac{r}{2} log r.

Lemma 4. If r = 3, then f(x) has on the simplex {x : x_{σ} ≥ 0, ∑ x_{σ} = 1} a unique global maximum at x = x^{∗}.

We postpone the proof of this lemma.

We conjecture that the lemma is true also for r > 3, but we have not been able to verify it; this is the reason Lemma 4 and Theorem 5 are restricted to r = 3. (If r = 2, f vanishes identically and the lemma fails.)

For any r such that the lemma is true (in particular for r = 3), the sum in (7.4) is dominated by terms with x − x^{∗} small, say |x − x^{∗}| < n^{−3/8}. For such x we use the Taylor expansion

f(x) = f(x^{∗}) − \frac{1}{2}(x − x^{∗})^{t}B(x − x^{∗}) + O(|x − x^{∗}|^{3}),

where −B is the matrix (\frac{∂^{2}f}{∂x_{σ}∂x_{τ}} (x^{∗})) of second derivatives of f at x^{∗}. We will shortly see that B is non-singular, and since x^{∗} is a maximum point, B has to be positive definite on the hyperplane ∑ x_{σ} = 0.

We now approximate the sum in (7.4) by an r! − 1 dimensional integral. We fix an arbitrary permutation σ_{0} and write d̂x for ∏_{σ≠σ_{0}} dx_{σ}. Given that ∑_{σ} x_{σ}n = n, an even integer, the conditions that y_{ij}n be even for all i, j ∈ {1, …, r − 1} yield (r − 1)^{2} linearly independent conditions (over GF (2)) that imply that also the remaining y_{ij}n are even. Hence only 2^{−(r−1)^{2}} of the possible values of (x_{σ}n mod 2)_{σ} are allowed. We thus obtain,

E U^{2} ∼

∫_{∑ x_{σ}=1} 2^{(r^{2}−1)/2}(2πn)^{(1−r!)/2}(r!)^{r!/2} (\frac{r!}{r^{r/2}} e^{f(x^{∗})})^{n} e^{− \frac{1}{2} n(x−x^{∗})B(x−x^{∗})}2^{−(r−1)^{2}}n^{r!−1}d̂x.

This Gaussian integral may be evaluated by several methods. For reference we state one method as a lemma, whose proof we omit.

Lemma 5. Suppose that B is a non-singular symmetric N × N matrix which is positive definite on the hyperplane ∑ x_{i} = 0 and such that (1, …, 1) is an eigenvector with eigenvalue λ_{1}. Then

∫_{∑ x_{i}=0} e^{− \frac{1}{2} x^{t}Bx}d̂x = \frac{1}{\sqrt{N}} (2π)^{(N−1)/2} (\frac{λ_{1}}{|B|})^{1/2} . □

The second derivatives of f are given by

\frac{∂^{2}f}{∂x_{σ}∂x_{τ}} = −\frac{1}{x_{σ}} δ_{στ} + \frac{1}{2} ∑_{i:σ(i)=τ(i)} \frac{1}{y_{ij}}

and thus

B = (r!δ_{στ} − \frac{r}{2}|\{i : σ(i) = τ(i)\}|)_{στ} .

It follows that (1, …, 1) is an eigenvector of B with eigenvalue λ_{1} = (1 − \frac{r}{2}) r!. Moreover, the determinant is given by

|B| = λ_{1} (\frac{r − 2}{2(r − 1)}r!)^{(r−1)^{2}} r!^{r!−1−(r−1)^{2}}

by an argument using group representation theory, which shows that B has besides λ_{1} the eigenvalues \frac{r−2}{2(r−1)}r! with multiplicity (r − 1)^{2} and r! with multiplicity r! − (r − 1)^{2} − 1. We omit the details since the case r = 3 also can be easily verified by direct evaluation of the determinant. We thus obtain, for r such that Lemma 4 is valid,

E U^{2} ∼ 2^{(r^{2}−1)/2}r!^{r!/2} (\frac{r!}{r^{r/2}} )^{2n} 2^{−(r−1)^{2}}r!^{−1/2} (\frac{λ_{1}}{|B|})^{1/2}

= 2^{(r^{2}−1)/2−(r−1)^{2}} (\frac{2(r − 1)}{r − 2})^{(r−1)^{2}/2} (\frac{r!}{r^{r/2}} )^{2n}

= 2^{r−1} (\frac{r − 1}{r − 2})^{(r−1)^{2}/2} (\frac{r!}{r^{r/2}} )^{2n}

and

E U^{2}/(E U)^{2} ∼ (\frac{r − 1}{r − 2})^{(r−1)^{2}/2} . □

Proof of Lemma 4. Let us first assume that x is an extreme point with every x_{σ} > 0. By the Lagrange multiplier method, there exists λ such that for all σ

λ = \frac{∂f}{∂x_{σ}} = − log x_{σ} − 1 + \frac{1}{2} ∑_{i} (log y_{iσ(i)} + 1)

and thus for a = exp(2λ + 2 − r) > 0,

ax_{σ}^{2} = ∏_{i} y_{iσ(i)}.  (7.5)

We now employ the special properties of r = 3. We relabel the x_{σ} as x_{1}, x_{2}, x_{3}, x′_{1}, x′_{2}, x′_{3}, with the x_{i} corresponding to even permutations σ, and x′_{i} to odd ones. It is easily seen that each y_{ij} is a sum x_{σ_{1}} + x_{σ_{2}} where one of the permutations is even and the other odd, i.e. y_{ij} = x_{k} + x′_{l} for some k and l.

Hence, if σ is even, y_{iσ(i)} = x_{σ} + x_{τ}, where τ runs through the three odd permutations for i = 1, 2, 3. Hence (7.5) yields

ax_{i}^{2} = ∏_{j}(x_{i} + x′_{j})  (7.6)

and similarly

ax′_{j}^{2} = ∏_{i}(x_{i} + x′_{j}).  (7.7)

Consider now the polynomial

p(x) = ∏_{j}(x + x′_{j}) − ∏_{i}(x − x_{i}) − ax^{2}

which has degree at most 2 and is not identically zero because p(0) = ∏_{j} x′_{j} + ∏_{i} x_{i} > 0. By (7.6) and (7.7), x_{1}, x_{2}, x_{3}, −x′_{1}, −x′_{2}, −x′_{3} are all roots, and this is possible only if x_{1} = x_{2} = x_{3} and x′_{1} = x′_{2} = x′_{3}. (7.6) and (7.7) now yield ax_{i}^{2} = (x_{1} + x′_{1})^{3} = ax′_{j}^{2}, and thus also x_{i} = x′_{j}; hence x = x^{∗}.

This shows that x^{∗} is the only extreme point in the interior of the simplex.

Now suppose that x is a maximum point at the boundary. If x_{σ} = 0 but y_{iσ(i)} > 0 for all i, then increasing x_{σ} to ε > 0, at the expense of some positive x_{τ}, with increase f(x) by −ε log ε + O(ε) > 0 if ε is small; similarly, if only one y_{iσ(i)} = 0, f(x) will increase by −\frac{1}{2}ε log ε + O(ε) > 0. It follows that if x is a maximum point, then y_{iσ(i)} = 0 for at least two i whenever x_{σ} = 0. This implies easily that x_{σ} ≠ 0 for at most one odd and one even permutation, τ and ν, say, but then of the nine y_{ij}, four equal 0, two equal x_{τ} and two x_{ν}, and one equal x_{τ} + x_{ν} = 1. Hence f(x) = 0 < f(x^{∗}), which completes the proof that the global maximum is attained at x^{∗}, and only there. □

References

1. A. D. Barbour, S. Janson, M. Karoński and A. Ruciński, Small cliques in random graphs, Random Struct. Alg. 1 (1990), 403–434.

2. E.A. Bender and E.R. Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Combin. Th. A 24 (1978), 296–307.

3. P. Billingsley, Convergence of Probability Measures, Wiley, New York, 1968.

4. B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Europ. J. Combinatorics 1 (1980), 311–316.

5. B. Bollobás, Random Graphs, Academic Press, London, 1985.

6. B. Bollobás and B.D. McKay, The number of matchings in random regular graphs and bipartite graphs, J. Combin. Th. B 41 (1986), 80–91.

7. C. Cooper, A. Frieze and M. Molloy, Hamilton cycles in random regular digraphs (to appear).

8. C. Cooper, A. Frieze, M. Molloy and B. Reed, Perfect matchings in random r-regular, s-uniform hypergraphs (to appear).

9. A.M. Frieze, M.R. Jerrum, M. Molloy, R. Robinson and N. Wormald, Generating and counting Hamilton cycles in random regular graphs (to appear).

10. A. Frieze and S. Suen, Counting Hamilton cycles in random directed graphs, Random Struct. Alg. 3 (1992), 235–242.

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

12. S. Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combinatorics, Probability and Computing 3 (1994), 97–126.

13. L. Le Cam, Locally asymptotically normal families of distributions, Univ. of California Publ. in Statistics 3 (1960), 37–98.

14. L. Le Cam, Théorie asymptotique de la décision statistique, Les Presses de l’Université de Montréal, Montreal, 1969.

15. L. Le Cam, Asymptotic methods in statistical decision theory, Springer-Verlag, New York, 1986.

16. M. Loève, Probability theory, 4th ed., Springer-Verlag, New York, 1977.

17. M. Molloy, H. Robalewska-Szarłat, R.W. Robinson and N.C. Wormald, 1-factorisations of random regular graphs, in preparation.

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

19. R.W. Robinson and N.C. Wormald, Existence of long cycles in random cubic graphs, Enumeration and Design (D.M. Jackson and S.A. Vanstone, eds.), Academic Press, Toronto, 1984, pp. 251–270.

20. R.W. Robinson and N.C. Wormald, Almost all cubic graphs are hamiltonian, Random Struct. Alg. 3 (1992), 117–125.

21. R.W. Robinson and N.C. Wormald, Almost all regular graphs are hamiltonian, Random Struct. Alg. 5 (1994), 363–374.

22. G. Roussas, Contiguity of probability measures: some applications in statistics, Cambridge Univ. Press, Cambridge, 1972.

23. A.V. Skorokhod, Limit theorems for stochastic processes, Teor. Veroyatnost. i Primenen. 1 (1956), 289–319 (Russian); English transl., Theor. Probab. Appl. 1 (1956), 261–290.

24. N.C. Wormald, The asymptotic distribution of short cycles in random regular graphs, J. Combin. Th. B 31 (1981), 168–182.

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

   E-mail address: svante.janson@math.uu.se