Permutation pseudographs and contiguity

Catherine Greenhill^{∗}

Department of Mathematics and Statistics,

University of Melbourne Parkville, VIC 3010, Australia

         csg@ms.unimelb.edu.au

Svante Janson^{†}

Department of Mathematics, Uppsala University, S-751 06 Uppsala, Sweden

                                              svante@math.uu.se

Jeong Han Kim^{‡}

Microsoft Research, One Microsoft Way,

Redmond, WA 98052, USA

   jehkim@microsoft.com

Nicholas C. Wormald^{§}

Department of Mathematics and Statistics, University of Melbourne Parkville, VIC 3010, Australia

                                     nick@ms.unimelb.edu.au

30 August 2001

Abstract

The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1, 2, …, n} uniformly at random and taking the n edges {i, σ(i)}. We prove several contiguity results involving permutation pseudographs (contiguity is a kind of asymptotic equivalence of sequences of probability spaces). Namely, we show that a random 4-regular pseudograph is contiguous with the sum of two permutation pseudographs, the sum of a permutation pseudograph and a random Hamilton cycle, and the sum of a permutation pseudograph and a random 2-regular pseudograph. (The sum of two random pseudograph spaces is defined by choosing a pseudograph from each space independently and taking the union of the edges of the two pseudographs.) All these results are proved simultaneously by working in a general setting, where each cycle of the permutation is given a nonnegative constant multiplicative weight. A further contiguity result is proved involving the union of a weighted permutation pseudograph and a random regular graph of arbitrary degree. All corresponding results for simple graphs are obtained as corollaries.

∗Research supported by an Australian Research Council Postdoctoral Fellowship.

†Research performed in part while visiting Microsoft Research.

‡Research performed in part while visiting the University of Melbourne.

§Research supported in part by the Australian Research Council and performed in part while visiting Microsoft Research.

1 Introduction

Recently, Kim and Wormald [7] showed that a random d-regular graph, for d even, asymptotically almost surely (a.a.s.) has an edge-decomposition into Hamilton cycles. This was done by proving the asymptotic equivalence (or contiguity) of two different probability models of random 4-regular graphs. The purpose of this paper is to prove similar contiguity results for various models where Hamilton cycles are replaced by permutation pseudographs, thereby confirming several conjectures of Janson [6, 5]. First we introduce some necessary notation.

Denote by G_{n,d} the uniform probability space of d-regular graphs on n vertices, where dn is even. As is usual in this area, we approach random d-regular graphs via the standard pairing model (see Bollobás [1]). Consider dn labelled points, with d points in each of n buckets, and take a random perfect matching of the points. We call this uniform probability space P_{n,d}. Letting the buckets be vertices and each pair represent an edge (joining the buckets containing the two endpoints of the pair), we obtain a random regular pseudograph (which may have loops or multiple edges). Denote this probability space by G_{n,d}^{∗}. Graphs with no loops or multiple edges occur with equal probabilities, so the restriction of G_{n,d}^{∗} to (simple) graphs gives the uniform probability space G_{n,d}. Also let G′_{n,d} be the space G_{n,d}^{∗} restricted to pseudographs with no loops (but which may still have multiple edges).

We can also form a random 2-regular pseudograph as follows: choose a permutation σ ∈ Sym(n) uniformly at random, and take the n edges {i, σ(i)}. The probability space of 2-regular pseudographs which results is called the permutation pseudograph model. Conditioning on no loops or multiple edges, we obtain the permutation graph model.

Suppose that (B_{n})_{n≥1} and (B̂_{n})_{n≥1} are two sequences of probability spaces such that B_{n} and B̂_{n} have the same underlying set Ω_{n} and differ only in the probabilities, for n ≥ 1. We say that these sequences are contiguous if, for any sequence of events (A_{n})_{n≥1} where A_{n} ⊆ Ω_{n} for n ≥ 1, we have

lim_{n→∞} P_{B_{n}}(A_{n}) = 1  if and only if  lim_{n→∞} PB̂_{n}(A_{n}) = 1.

In other words, an event A_{n} is a.a.s. true in B_{n} if and only if it is a.a.s. true in B̂_{n}. (Here a.a.s. stands for “asymptotically almost surely”, meaning “with probability which tends to 1 as n → ∞”.) In this case, write

B_{n} ≈ B̂_{n}.

For more information on contiguity see [6, Sections 9.5,9.6] or [14, Section 4].

We will also need the definition of the sum of two pseudograph models. If G and Ĝ are two probability spaces of random graphs or pseudographs on the same vertex set, then their sum G+Ĝ is the space whose elements are defined by the random pseudograph G ∪ Ĝ, where G ∈ G and Ĝ ∈ Ĝ are generated independently. The graph-restricted sum of G and Ĝ, denoted G ⊕Ĝ, is the space which is the restriction of G +Ĝ to simple graphs.

We will prove three new contiguity results involving permutation pseudographs. Informally, we will show that the sum of two permutation pseudographs, or of a permutation pseudograph and a random Hamilton cycle, or of a permutation pseudograph and a random 2-regular pseudograph, are all contiguous with a random 4-regular pseudograph. (In the above, the term “random regular pseudograph” refers to the model G_{n,d}^{∗} which arises from the pairings model.) By conditioning on having no loops or multiple edges, we obtain the corresponding results for graphs. All the pseudograph results are proved simultaneously by placing the problems in a common general setting. In fact, we will also obtain some previously-known contiguity results for free. This general setting is now described.

Let θ ≥ 0 be some constant. Give each permutation σ ∈ Sym(n) the weight

θ^{κ(σ)−1},

where κ(σ) is the number of cycles in (the disjoint cycle decomposition of) σ, and choose σ ∈ Sym(n) with probability proportional to its weight. Then form a 2-regular pseudograph G on n vertices, by taking the n edges {i, σ(i)}, as above. Let κ(G) be the number of cycles in G, and let ν(G) be the number of cycles in G of length 1 or 2, for G ∈ G_{n,2}^{∗}. Each G ∈ G_{n,2}^{∗} arises from exactly 2^{κ(G)−ν(G)} permutations. If σ is chosen with probability proportional to θ^{κ(σ)−1}, then G occurs with probability proportional to

W_{θ}(G) = θ^{κ(G)−1} 2^{κ(G)−ν(G)}.

Let F_{n}(θ) be the model of random 2-regular pseudographs obtained in this way. We denote this as

F_{n}(θ) = (G_{n,2}^{∗})^{(W_{θ})} .

So F_{n}(θ) is the model of 2-regular pseudographs obtained by choosing G with weight proportional to W_{θ}(G). When θ = 1 we obtain the permutation pseudograph model, as described above. When θ = 1/2 we obtain G_{n,2}^{∗}. To see this, note that the weight of G in G_{n,2}^{∗} is 2^{n−ν(G)}, which is proportional to W_{1/2}(G). Finally, when θ = 0 the only pseudographs with nonzero weight are those with κ(G) = 1; namely, Hamilton cycles. Each Hamilton cycle gets the same weight, so we obtain H_{n}, the space of uniform Hamilton cycles on n vertices.

Before stating our main result, we make a few remarks. When θ > 0 it is equivalent, and customary, to use the weight θ^{κ(σ)} instead; our choice covers the case θ = 0 too. It is well-known (see for example [13, (3.5.2)]) that the sum of the weights θ^{κ(σ)−1} over the n! permutations in Sym(n) equals (θ + 1)(θ + 2) ⋯ (θ + n − 1). Hence the probability of choosing a given permutation σ is θ^{κ(σ)−1}/(θ + 1) ⋯ (θ + n − 1).

The distribution of random permutations defined by these weights appears in several contexts, for example in the so-called Chinese restaurant process [11, Section 6.3]. The joint distribution of the number of cycles of various lengths for these random permutations, or equivalently for F_{n}(θ), appears in several further contexts, and is known as the Ewens sampling formula. See [11, 12] for a survey.

Our main result is the following. For the proof we use the small subgraph conditioning method introduced in [9, 10] by Robinson and Wormald.

Theorem 1.1. Let θ_{1}, θ_{2} ≥ 0 be constants. Then

F_{n}(θ_{1}) + F_{n}(θ_{2}) ≈ G_{n,4}^{∗}

except in the case θ_{1} = θ_{2} = 0, when

F_{n}(θ_{1}) + F_{n}(θ_{2}) ≈ G′_{n,4}.

The exception for θ_{1} = θ_{2} = 0 is natural, since this is the only case where F_{n}(θ_{1}) + F_{n}(θ_{2}) is loopless.

As corollaries we obtain the corresponding results for (simple) graphs, by considering the graph-restricted sum: i.e. by conditioning on F_{n}(θ_{1}) + F_{n}(θ_{2}) being a graph (see Corollary 1.1).

As particular cases of Theorem 1.1, we obtain several new results involving permutation pseudographs. Let F_{n} = F_{n}(1) denote the permutation pseudograph model. By taking (θ_{1}, θ_{2}) =(0,1), (\frac{1}{2}, 1) and (1, 1), we show that the three models

H_{n} + F_{n},  G_{n,2}^{∗} + F_{n},  F_{n} + F_{n}

are all contiguous with G_{n,4}^{∗}. We also obtain the known results

H_{n} + H_{n} ≈ G′_{n,4}

(see [7]) by setting (θ_{1}, θ_{2}) = (0, 0),

H_{n} + G_{n,2}^{∗} ≈ G_{n,4}^{∗}

(see [4, 10]) by setting (θ_{1}, θ_{2}) = (0, \frac{1}{2}), and

G_{n,2}^{∗} + G_{n,2}^{∗} ≈ G_{n,4}^{∗}

(see [8]) by setting (θ_{1}, θ_{2}) = (\frac{1}{2}, \frac{1}{2}).

Note that one consequence of these results is

F_{n} + F_{n} ≈ H_{n} + G_{n,2}^{∗},

showing that the sum of two permutation pseudographs is a.a.s. Hamiltonian. This was proved directly by Frieze [3].

In the final section we prove the following result, using the same method.

Theorem 1.2. Let θ ≥ 0 be constant, and d ≥ 3. Then

F_{n}(θ) + G_{n,d−2}^{∗} ≈ G_{n,d}^{∗}

except when θ = 0 and d = 3, when

F_{n}(0) + G_{n,1}^{∗} ≈ G′_{n,3}.

In particular, by setting θ = 1, we prove the following contiguity result for permutation pseudographs:

F_{n} + G_{n,d−2}^{∗} ≈ G_{n,d}^{∗}

for d ≥ 3. (This result was claimed in [6, Section 9.5].) The theorem also captures several known results: for θ = 0 we obtain

H_{n} + G_{n,1}^{∗} ≈ G′_{n,3}

and

H_{n} + G_{n,d−2}^{∗} ≈ G_{n,d}^{∗}

for d ≥ 4, see [4, 5]. For θ = \frac{1}{2} we obtain

G_{n,2}^{∗} + G_{n,d−2}^{∗} ≈ G_{n,d}^{∗}

see [8].

Theorems 1.1 and 1.2 confirm all the conjectures of Janson relating to permutation pseudographs (see [5] and the end of [6, Section 9.5]), and imply the following extension of [6, Theorem 9.43] for sums of several random pseudographs.

Theorem 1.3. Let m ≥ 1 and let d_{1}, …, d_{m} ≥ 1. Let G_{1}, …, G_{m} be independent random pseudographs such that G_{i} is a copy of G_{n,d_{i}}^{∗} when d_{i} ≠ 2, and a copy of F_{n}(θ_{i}), for arbitrary constant θ_{i} ≥ 0, when d_{i} = 2. If d = d_{1} + ⋯ + d_{m} ≥ 3, then

G_{1} + ⋯ + G_{m} ≈ G_{n,d}^{∗}

except when the only summands are G_{n,1}^{∗} and F_{n}(0) = H_{n}, in which case

G_{1} + ⋯ + G_{m} ≈ G′_{n,d}.

As an application, this implies that the a.a.s. result by Friedman [2] on the second eigenvalue of F_{n} + ⋯ + F_{n} applies also to G_{n,2d}^{∗} (and to G_{n,2d}).

Note however that no two of the models F_{n}(θ) are contiguous. This follows from [6, Corollary 9.54] and the standard fact [11] that the number of cycles of length k in F_{n}(θ) is asymptotically Poisson with mean θ/k, for k ≥ 1, with the numbers for different lengths asymptotically independent.

By conditioning on no loops and multiple edges in Theorem 1.3, we obtain all corresponding results for simple graphs.

Corollary 1.1. Let m ≥ 1 and let d_{1}, …, d_{m} ≥ 1. Let G_{1}, …, G_{m} be independent random pseudographs such that G_{i} is a copy of G_{n,d_{i}}^{∗} when d_{i} ≠ 2, and a copy of F_{n}(θ_{i}), for arbitrary constant θ_{i} ≥ 0, when d_{i} = 2. If d = d_{1} + ⋯ + d_{m} ≥ 3, then

G_{1} ⊕ ⋯ ⊕ G_{m} ≈ G_{n,d}.

Finally, note that Janson [5, Theorem 12] showed that G_{n,d}^{∗} is contiguous with the uniform model of d-regular pseudographs on n vertices. Therefore all of our results hold using uniformly distributed regular pseudographs instead of the models G_{n,d}^{∗} which arise from the pairing model.

1.1 Further notation and preliminary results

Our proofs use the small subgraph conditioning method, stated below. Before stating the theorem we introduce some notation. Let G be a probability space with underlying set Ω. Given any nonnegative random variable Y on G, denote by G^{(Y)} the probability space with underlying set Ω and probabilities given by

P_{G^{(Y )}}(X) = \frac{Y (X)P_{G}(X)}{Z}

for all X ∈ Ω, where Z = ∑_{X∈Ω} Y (X) is the normalising constant. The notation [X]_{k} denotes the falling factorial, [X]_{k} = X(X − 1) ⋯ (X − k + 1). (Later we use [x] with no subscript to denote extraction of coefficients.)

The following statement of the small subgraph conditioning method is taken from [14]. A similar theorem is given in [6, Theorem 9.12].

Theorem 1.4 ([14], Theorem 4.1). Let λ_{i} > 0 and δ_{i} ≥ −1 be real numbers for i = 1, 2, … and suppose that for each n there are random variables X_{i} = X_{i}(n), i = 1, 2, … and Y = Y (n), all defined on the same probability space G = G_{n} such that X_{i} is nonnegative integer valued, Y is nonnegative and EY > 0 (for n sufficiently large). Suppose furthermore that

(i) For each k ≥ 1, the variables X_{1}, …, X_{k} are asymptotically independent Poisson random variables with EX_{i} → λ_{i},

(ii)

\frac{E(Y [X_{1}]_{j_{1}} ⋯ [X_{k}]_{j_{k}})}{EY} → ∏_{i=1}^{k}(λ_{i}(1 + δ_{i}))^{j_{i}}

for every finite sequence j_{1}, …, j_{k} of nonnegative integers,

(iii) ∑_{i} λ_{i} δ_{i}^{2} < ∞,

(iv) EY^{2}/(EY)^{2} ≤ exp(∑_{i} λ_{i} δ_{i}^{2}) + o(1) as n → ∞.

Then

Ḡ^{(Y)} ≈ Ḡ

where Ḡ is the probability space obtained from G by conditioning on the event ∧_{δ_{i}=−1}(X_{i} = 0).

As with many contiguity results for graphs, it is most convenient to perform the calculations at the pairings level. In F_{n}(θ), the pseudograph G is given weight W_{θ}(G). If we divide this weight evenly among the 2^{n−ν(G)} pairings corresponding to G, then a pairing P ∈ P_{n,2} corresponding to G receives weight

θ^{κ(G)−1} 2^{κ(G)−ν(G)} 2^{ν(G)−n} = 2^{1−n}(2θ)^{κ(G)−1}.

That is, the pairing P ∈ P_{n,2} has weight which is proportional to

w_{θ}(P) = (2θ)^{κ(P)−1}.

(This demonstrates that F_{n}(\frac{1}{2}) = G_{n,2}^{∗}, since then P is chosen uniformly.) Let F̂_{n}(θ) = P_{n,2}^{(w_{θ})}; that is, the probability space of pairings in P_{n,2} where pairing P receives weight w_{θ}(P) = (2θ)^{κ(P)−1}. For θ_{1}, θ_{2} ≥ 0, unless (θ_{1}, θ_{2}) = (0, 0) we show that

F̂_{n}(θ_{1}) + F̂_{n}(θ_{2}) ≈ P_{n,4}.

Here ‘+’ denotes combining two pairings of disjoint sets of points by merging the corresponding buckets and randomly relabelling the points in each resulting bucket. In the exceptional case θ_{1} = θ_{2} = 0, we obtain

F̂_{n}(0) + F̂_{n}(0) ≈ P′_{n,4},

where P′_{n,4} is P_{n,4} conditioned on no loops; i.e., no pair has both ends in the same bucket.

We now define the random variable Y which will be analysed. Fix constants θ_{1}, θ_{2} ≥ 0. Let (F_{1}, F_{2}) be a partition of the pairs of a pairing P ∈ P_{n,4} such that exactly two points in each bucket belong to F_{1} (and hence exactly two points in each bucket belong to F_{2}). The pseudograph on n vertices corresponding to F_{i} is 2-regular, for i = 1, 2. Call such a partition an F -decomposition of P, and write (F_{1}, F_{2}) ⊢ P. Now F_{i} gives rise to a unique pairing F̃_{i} ∈ P_{n,2}, for i = 1, 2, using the ordering on the points in P to order the points in each bucket in F̃_{i}. Hence we can define κ(F_{i}) = κ(F̃_{i}), G(F_{i}) = G(F̃_{i}), and so on. In what follows we will drop the tilde sign where there is no chance of confusion. Now define Y (P) by

Y (P) = ∑_{(F_{1},F_{2})⊢P}(2θ_{1})^{κ(F_{1})−1} (2θ_{2})^{κ(F_{2})−1}  (1)

where the sum is over all F -decompositions of P. Note that

P_{n,4}^{(Y)} = F̂_{n}(θ_{1}) + F̂_{n}(θ_{2}),

since Y (P) is proportional to P_{F̂_{n}(θ_{1})+F̂_{n}(θ_{2})}(P). Therefore it suffices to establish that Y satisfies the requirements of Theorem 1.4. The variables X_{i} will be the number of cycles of length i in the pairing.

The following lemma will be useful.

Lemma 1.1. If c ≥ 0 then

∑_{F ∈P_{n,2}} c^{κ(F)−1} ∼ \frac{2^{n} n!}{2Γ(c/2 + 1)} n^{c/2−1}.

Proof. It is not difficult to see that

∑_{F ∈P_{n,2}} c^{κ(F)} = 2^{n} ∑_{σ∈Sym(n)} (\frac{c}{2})^{κ(σ)} .

Assume for the time being that c > 0. Using [13, (3.5.2)] for example, we can write

∑_{F ∈P_{n,2}} c^{κ(F)} = 2^{n} \frac{c}{2} (\frac{c}{2} + 1) ⋯ (\frac{c}{2} + n − 1) = \frac{2^{n} Γ(c/2 + n)}{Γ(c/2)}.

Therefore

∑_{F ∈P_{n,2}} c^{κ(F)−1} = \frac{2^{n}Γ(c/2 + n)}{2Γ(c/2 + 1)} ∼ \frac{2^{n} n!}{2Γ(c/2 + 1)} n^{c/2−1},

and this equation holds by continuity even when c = 0.

Taking c = 1 we recover the standard formula

|P_{n,2}| ∼ (πn)^{−1/2} 2^{n}n!.

Dividing by |P_{n,2}| we find:

Corollary 1.2. If c ≥ 0 then

E(c^{κ(F)−1}) ∼ \frac{\sqrt{π}}{2Γ(c/2 + 1)} n^{(c−1)/2}

where the expectation is over F ∈ P_{n,2}.

2 Calculating the Expectation

To calculate the expectation of Y we use a slightly different expression. For G ∈ G_{n,4}^{∗} let Y (G) be defined by

Y (G) = ∑_{G(P)=G^{P ∈P_{n,4}}} Y (P).

Suppose that G(F̃_{1}) ∪ G(F̃_{2}) = G for F̃_{1}, F̃_{2} ∈ P_{n,2}. There are exactly 6^{n} ways to produce ordered pairs (F_{1}, F_{2}) such that F_{i} corresponds to F̃_{i} for i = 1, 2, since all we must do is specify which 2 points correspond to F_{1}, for each bucket of 4 points. Each such ordered pair is an F -decomposition for a pairing P corresponding to G. Summing over all such F̃_{1}, F̃_{2} gives all the ways which a pairing P corresponding to G can arise. Hence (dropping the tilde signs again), Y (G) can also be written as

Y (G) = 6^{n} ∑_{G(F_{1})∪G(F_{2})=G^{(F_{1},F_{2})∈P_{n,2}×P_{n,2}}}(2θ_{1})^{κ(F_{1})−1}(2θ_{2})^{κ(F_{2})−1}.

Therefore the expectation of Y (P) in P_{n,4} is given by

EY = \frac{1}{|P_{n,4}|} ∑_{G∈G_{n,4}^{∗}} Y (G)

= \frac{6^{n}}{|P_{n,4}|} ∏_{i=1}^{2} ( ∑_{F ∈P_{n,2}} (2θ_{i})^{κ(F)−1})

∼ \frac{24^{n} n!^{2}}{4|P_{n,4}|Γ(θ_{1} + 1)Γ(θ_{2} + 1)} n^{θ_{1}+θ_{2}−2}
∼ \frac{\sqrt{2}π n^{θ_{1}+θ_{2}−1}}{4Γ(θ_{1} + 1)Γ(θ_{2} + 1)} (\frac{3}{2})^{n} ,  (2)

using Lemma 1.1 and the formula

|P_{n,4}| = |P_{2n,2}| ∼ (2πn)^{−1/2} 2^{2n}(2n)! ∼ \frac{2^{4n} n!^{2}}{\sqrt{2}πn} .

3 Calculating the Variance

We are interested in the expected value of Y (P)^{2}. Now

E(Y^{2}) = \frac{1}{|P_{n,4}|} ∑_{P ∈P_{n,4}} ∑_{(F_{1},F_{2})⊢P} (2θ_{1})^{κ(F_{1})−1} (2θ_{2})^{κ(F_{2})−1} ∑_{(F_{3},F_{4})⊢P} (2θ_{1})^{κ(F_{3})−1} (2θ_{2})^{κ(F_{4})−1}.

We follow the same steps used by Kim and Wormald [7] in the analysis of the variance of H_{2} (the number of H-decompositions of a pairing in P_{n,4}, where an H-decomposition is a partition of a pairing into two subsets, each of which corresponds to a Hamilton cycle). In fact, it will be convenient later to compare our analysis directly with the analysis of E(H_{2}^{2}) given in [7], since the most technical part of both arguments is identical.

Given P ∈ P_{n,4}, let ((F_{1}, F_{2}), (F_{3}, F_{4})) be an ordered pair of F -decompositions of P. A pair in P is of type (i, j) if it belongs to F_{i} and F_{2+j}, for 1 ≤ i, j ≤ 2. We use the same notation for the corresponding edge in G(P). As in [7], a vertex in G(P) is said to have

• type A if an edge of each type is incident with it,

• type B if there are two (1, 1)-edges and two (2, 2)-edges incident with it,

• type C if there are two (1, 2)-edges and two (2, 1)-edges incident with it

(note that these are the only possibilities). Consider the edges of a given type (i, j). Each such edge lies on either a closed cycle, or a path which starts and ends in type A vertices. These cycles and paths are disjoint. Each type A vertex is the endpoint of a path of type (i, j). It follows that the number of type A vertices is even. Moreover, a closed cycle of (i, j) edges contains only type B vertices if i = j, and it contains only type C vertices if i ≠ j. Each type B vertex must lie on a path or cycle of type (1, 1) edges, and a path or cycle of type (2, 2) edges. Similarly, each type C vertex must lie on a path or cycle of type (1, 2) edges, and a path or cycle of type (2, 1) edges.

By ignoring the type B and type C vertices, the edges of any particular type give rise to a perfect matching on the type A vertices. The union of these four perfect matchings gives a labelled 4-regular pseudograph on the type A vertices, called a connection scheme. We proceed by calculating the contribution to the weight made by all possible connection schemes, and then the contribution made from all possible ways to add back the type B and type C vertices. Finally we calculate the number of pairings corresponding to each such configuration.

Suppose that there are a = 2k type A vertices, b type B vertices and c type C vertices, so that c = n − 2k − b. There are

\binom{n}{2k}\binom{n − 2k}{b} = \frac{n!}{(2k)! b! c!}

ways to assign types to vertices. The contribution from all possible connection schemes is given by

S(2k) = ∑_{(M_{1},M_{2},M_{3},M_{4})}(2θ_{1})^{κ(M_{1}∪M_{2})+κ(M_{2}∪M_{3})−2} (2θ_{2})^{κ(M_{3}∪M_{4})+κ(M_{4}∪M_{1})−2},

where M_{ℓ} is a perfect matching on [2k] for 1 ≤ ℓ ≤ 4. To see why this is the correct quantity to analyse, let M_{1}, M_{2}, M_{3}, M_{4} be the matchings induced by the edges of types (1, 2), (1, 1), (2, 1) and (2, 2), respectively. Then each M_{ℓ} ∪ M_{ℓ+1} forms the edges of the connection scheme induced by one of the permutation pseudographs F_{i}, namely M_{1} ∪ M_{2} = F_{1}, M_{2} ∪ M_{3} = F_{3}, M_{3} ∪ M_{4} = F_{2} and M_{4} ∪ M_{1} = F_{4}. Thus for example, a cycle in M_{1} ∪ M_{2} gives rise to a (possibly larger) cycle in F_{1}. Therefore we weight each such cycle by a factor of 2θ_{1}. Analysis of S(2k) is deferred until Section 6, where we prove in Theorem 6.1 that

S(2k) ∼ \frac{π^{2}k^{2t−2} (2k)!^{4}}{16^{k+1}Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2} k!^{4}}

where t = θ_{1} + θ_{2}.

(This assumes that k → ∞. However, this behaviour of k can be assumed, as we can see by applying the following analysis to the case of bounded k.)

We now have to add in the type B and type C vertices. We can think of the four edge-labels (i, j) as colours. First consider adding the type B vertices onto type (1, 1) edges. Recall that all the vertices are already labelled. Some of the type B vertices slide on to the edges between the type A vertices. If there are s vertices on an edge then there are s! ways to arrange them. Hence the e.g.f. for vertices on a single edge is 1/(1 − x), so the e.g.f. for vertices on the k edges is 1/(1 − x)^{k}. Note that sliding type B vertices onto these edges does not affect the number of cycles in the resulting pairing. Any remaining type B vertices form closed cycles of type (1, 1) edges. Any such cycle of (1, 1) edges forms a cycle in both F_{1} and F_{3} (indeed any monochromatic cycle forms a cycle in two of the F_{i}). Hence each such cycle should contribute weight factor 4θ_{1}^{2} to the corresponding pairing. For reasons which will become apparent later, we will instead weight an s-cycle of (1, 1) edges by a factor of 4θ_{1}^{2} if s ≥ 3, and by a factor of 2θ_{1}^{2} otherwise. Hence the e.g.f. for these weighted cycles is

2θ_{1}^{2} ∑_{s≥1} \frac{x^{s}}{s} = −2θ_{1}^{2} log(1 − x).  (3)

It follows that the e.g.f. for unions of these weighted cycles is

\frac{1}{(1 − x)^{2θ_{1}^{2}}} .

Finally, the total contribution from adding b vertices of type B onto the (1, 1) edges is

b! [x^{b}] \frac{1}{(1 − x)^{k}} · \frac{1}{(1 − x)^{2θ_{1}^{2}}} = b! \binom{k + b + 2θ_{1}^{2} − 1}{b} ∼ (\frac{k + b}{k})^{2θ_{1}^{2}−1} \frac{(k + b)!}{k!}.

(Here [x^{b}] means extraction of coefficients.) Note that the above calculation assumes that k → ∞. This behaviour of k can be assumed, as above.

When adding b vertices of type B onto the (2, 2) edges, the contribution is

(\frac{k + b}{k})^{2θ_{2}^{2}−1} \frac{(k + b)!}{k!}.

For type C vertices, a closed cycle of either (1, 2) or (2, 1) edges should be weighted 4θ_{1}θ_{2}. However, we will weight it by 4θ_{1}θ_{2} if it has length at least 3, and give it weight 2θ_{1}θ_{2} otherwise. The e.g.f. for unions of these weighted cycles is

\frac{1}{(1 − x)^{2θ_{1}θ_{2}}}

and the total contribution from adding c vertices of type C onto the (1, 2) edges, say, is

c! [x^{c}] \frac{1}{(1 − x)^{k}} · \frac{1}{(1 − x)^{2θ_{1}θ_{2}}} = c! \binom{k + c + 2θ_{1}θ_{2} − 1}{c} ∼ (\frac{k + c}{k})^{2θ_{1}θ_{2}−1} \frac{(k + c)!}{k!}.

The contribution from adding c vertices of type C onto the (2, 1) edges is identical.

Identification of the two sets of type B vertices (those on type (1, 1) edges and those on type (2, 2) edges) is immediate, since they are already labelled, and gives no extra factor in the weighting. Similarly, there is no extra factor from identifying the two sets of type C vertices.

We now have a 4-regular pseudograph with edge labels (i, j). It remains to calculate the number of pairings corresponding to this pseudograph. There are 4! ways to wire up a given vertex into a pairing, unless the vertex lies in a monochromatic 1-cycle or a monochromatic 2-cycle. The presence of each such cycle decreases the number of corresponding pairings by a factor of 2. However, we have already penalised each monochromatic 1-cycle and 2-cycle by a factor of 2 (for example, in (3)). Therefore we can simply multiply by 4!^{n} at this stage.

Combining all this we obtain (where as above t = θ_{1} + θ_{2}),

|P_{n,4}|E(Y^{2})

∼ ∑_{k} ∑_{b} \frac{n!}{(2k)!b!c!} S(2k) (\frac{k + b}{k})^{2θ_{1}^{2}+2θ_{2}^{2}−2} (\frac{k + c}{k})^{4θ_{1}θ_{2}−2} \frac{(k + b)!^{2} (k + c)!^{2}}{k!^{4}} 4!^{n}

∼ ∑_{k} ∑_{b} \frac{π^{2} 4!^{n} (2k)!^{3} n! k^{2t−2} (k + b)^{2θ_{1}^{2}+2θ_{2}^{2}−2}(k + c)^{4θ_{1}θ_{2}−2} (k + b)!^{2} (k + c)!^{2}}{16^{k+1} k^{2t^{2}−4} Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2} b! c! k!^{8}} .

To treat this sum, we reduce it to the special case θ_{1} = θ_{2} = 0, already treated in [7]. (See also [4] for the case (θ_{1}, θ_{2}) = (0, \frac{1}{2}) and [8] for the case (θ_{1}, θ_{2}) = (\frac{1}{2}, \frac{1}{2}).) We thus write the last equation as

|P_{n,4}|E(Y^{2}) ∼ \frac{1}{Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2}} ∑_{k} ∑_{b} k^{2t−2t^{2}}(k + b)^{2θ_{1}^{2}+2θ_{2}^{2}}(k + c)^{4θ_{1}θ_{2}} s(k, b), (4)

where s(k, b) does not depend on θ_{1} or θ_{2}.

In the special case θ_{1} = θ_{2} = 0, when Y = H_{2}, this yields

|P_{n,4}|E(H_{2}^{2}) ∼ ∑_{k} ∑_{b} s(k, b).

This sum was analysed in [7], where it was shown that

s(k, b) ∼ \frac{4!^{n} π\sqrt{2n}}{16(k + b)(k + c)\sqrt{kbc}} (\frac{n}{e})^{2n} f(β, κ)

where here κ = k/n (and hence has nothing to do with our κ), β = b/n and

f(β, κ) = \frac{16^{κ} (β + κ)^{2(β+κ)} (1 − κ − β)^{2(1−κ−β)}}{(2κ)^{2κ} β^{β} (1 − 2κ − β)^{1−2κ−β}} .

Moreover, the analysis given in [7] shows that the maximum of f occurs at β = 1/6, κ = 1/3, and thus all terms s(k, b) with (k/n, b/n) outside a small neighbourhood around (1/3, 1/6) give an exponentially small contribution to the double sum. It follows that the sum in (4) is also dominated by terms with k ∼ n/3, b ∼ n/6, c ∼ n/6. Thus

|P_{n,4}|E(Y^{2}) ∼ \frac{1}{Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2}} ∑_{k} ∑_{b} (\frac{n}{3})^{2t−2t^{2}} (\frac{n}{2})^{2θ_{1}^{2}+2θ_{2}^{2}} (\frac{n}{2})^{4θ_{1}θ_{2}} s(k, b)

= \frac{2^{−2t^{2}}3^{2t^{2}−2t}}{Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2}} n^{2t} ∑_{k} ∑_{b} s(k, b)

∼ \frac{2^{−2t^{2}}3^{2t^{2}−2t}}{Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2}} n^{2t} |P_{n,4}| E(H_{2}^{2}).

Moreover, by comparing with the case θ_{1} = θ_{2} = 0 in (2), we find

EY ∼ \frac{n^{t}}{Γ(θ_{1} + 1)Γ(θ_{2} + 1)}EH_{2}.

Now recall from [7] that

\frac{E(H_{2}^{2})}{(EH_{2})^{2}} ∼ \sqrt{24}.

It follows that

\frac{E(Y^{2})}{(EY)^{2}} ∼ 2^{−2t^{2}} 3^{2t^{2}−2t} \frac{E(H_{2}^{2})}{(EH_{2})^{2}} = 2^{3/2−2t^{2}} 3^{2t^{2}−2t+1/2}.  (5)

4 Effect of short cycles

Again, the argument follows the steps used by Kim and Wormald in [7]. For fixed k ≥ 1, we must calculate

\frac{E(Y C_{k})}{EY}

where C_{k} is the number of k-cycles in P_{n,4}. (Here a k-cycle is a set of k pairs in P which correspond to a k-cycle in G(P).) To do this we calculate

|P_{n,4}| E(Y C_{k}) = ∑_{C} ∑_{C⊆P^{P ∈P_{n,4}}} Y (P),

where the first sum is over all possible labelled k-cycles C. Let C be a labelled, directed cycle on k vertices. There are

\frac{[n]_{k}}{k} ∼ \frac{n^{k}}{k}

choices for C. Edges of the cycle will correspond to pairs in a pairing P ∈ P_{n,4}, with an F -decomposition (F_{1}, F_{2}). Nominate which 2 points in each bucket will be joined to pairs in F_{1}. There are 6^{n} ways to nominate these points. Now we only need specify F_{1} and F_{2} as pairings on n buckets, each with 2 points. There are three possibilities:

(i) C ∩ F_{1} = C,

(ii) C ∩ F_{1} = ∅,

(iii) C ∩ F_{1} is the disjoint union of i paths, for some i ≥ 1.

First consider case (i). Here C forms a closed cycle in F_{1}. We must divide by 2 if C has length 3 or more, to undirect the cycle. Then wire C ∩ F_{1} into the specified points of the subpairing F_{1}. There are 2^{k} ways to do this if k ≥ 3, and 2^{k−1} ways if k = 1, 2. So in either case, the net effect is that of multiplying by 2^{k−1}. Finally, we multiply by 2θ_{1} to assign the appropriate weight to C. The contribution from extending C ∩ F_{1} to F_{1} is

∑_{F ∈P_{n−k,2}}(2θ_{1})^{κ(F)−1} ∼ \frac{2^{n−k} (n − k)! (n − k)^{θ_{1}−1}}{2Γ(θ_{1} + 1)} ∼ \frac{2^{n−k} n! n^{θ_{1}−1}}{2 n^{k} Γ(θ_{1} + 1)},

while the contribution from F_{2} is just

∑_{F ∈P_{n,2}}(2θ_{2})^{κ(F)−1} ∼ \frac{2^{n} n! n^{θ_{2}−1}}{2Γ(θ_{2} + 1)},

using Lemma 1.1. So using (2), the total contribution from case (i) is asymptotically equal to

\frac{θ_{1} 24^{n} n!^{2} n^{θ_{1}+θ_{2}−2}}{4k Γ(θ_{1} + 1)Γ(θ_{2} + 1)} ∼ |P_{n,4}| EY \frac{θ_{1}}{k} .

From case (ii) we similarly get a contribution of

|P_{n,4}| EY \frac{θ_{2}}{k} .

Now consider case (iii). Here C ∩ F_{2} is also the disjoint union of i paths. Colour pairs of F_{1} red and pairs of F_{2} blue. Each path (whether red or blue) consists of at least 1 edge. The number of ways to grow these 2i paths, starting from the least vertex in C and forming the paths in sequence red, blue, ... in the direction of the cycle, is

[x^{k}] (\frac{x}{1 − x})^{2i}

(see [7]). Shift the starting vertex around the cycle by 1 place, k times. Having done this for each directed cycle, we have counted each undirected configuration exactly 2i times. To account for this we multiply by k/(2i), and note that now we are working with undirected cycles.

Now we must wire F_{i} ∩C into the specified points of the subpairing F_{i}, and complete F_{i}, for i = 1, 2. Suppose that there are j edges in C ∩F_{1}. Then there are i+j nonisolated vertices in C ∩ F_{1}, and hence there are 2^{i+j} ways to wire up F_{1} ∩ C into the specified points of F_{1}. Shrink each of the i red paths in the subpairing down to a single bucket. This gives n − j buckets in total, each with 2 specified points. If we calculate the contribution from all possible pairings on these points, and then expand the red paths in C ∩ F_{1} back to their original size, we will have calculated the contribution from all ways of completing F_{1}. This is equal to

∑_{F ∈P_{n−j,2}} (2θ_{1})^{κ(F)−1} ∼ \frac{2^{n−j} (n − j)! (n − j)^{θ_{1}−1}}{2 Γ(θ_{1} + 1)} ∼ \frac{2^{n−j} n! n^{θ_{1}−1}}{2 n^{j} Γ(θ_{1} + 1)}  (6)

using Lemma 1.1. Similarly, there are 2^{i+(k−j)} ways to wire the blue paths into the specified points of the subpairing F_{2}, and the contribution from all ways of extending C ∩ F_{2} to F_{2} is asymptotically

\frac{2^{n−(k−j)} (n − (k − j))! (n − (k − j))^{θ_{2}−1}}{2Γ(θ_{2} + 1)} ∼ \frac{2^{n−(k−j)} n! n^{θ_{2}−1}}{2 n^{k−j} Γ(θ_{2} + 1)} .

Thus each decomposition of C into 2i paths with j red edges contributes asymptotically

2^{i+j} · \frac{2^{n−j} n! n^{θ_{1}−1}}{2 n^{j} Γ(θ_{1} + 1)} · 2^{i+k−j} · \frac{2^{n−(k−j)} n! n^{θ_{2}−1}}{2 n^{k−j} Γ(θ_{2} + 1)} = \frac{2^{2n+2i} n!^{2} n^{θ_{1}+θ_{2}−2}}{4n^{k} Γ(θ_{1} + 1)Γ(θ_{2} + 1)}.

Since this does not depend on j, and using (2) again, we find that the total contribution from case (iii) is asymptotically equal to

6^{n} · \frac{n^{k}}{k} ∑_{i≥1} [x^{k}] (\frac{x}{(1 − x)})^{2i} · \frac{k}{2i} \frac{2^{2n+2i}n!^{2}n^{θ_{1}+θ_{2}−2}}{4n^{k}Γ(θ_{1} + 1)Γ(θ_{2} + 1)}

= \frac{24^{n} n!^{2} n^{θ_{1}+θ_{2}−2}}{4Γ(θ_{1} + 1) Γ(θ_{2} + 1)}[x^{k}] ∑_{i≥1} (\frac{4x^{2}}{(1 − x)^{2}} )^{i} \frac{1}{2i}

∼ EY |P_{n,4}|[x^{k}] ∑_{i≥1} (\frac{4x^{2}}{(1 − x)^{2}} )^{i} \frac{1}{2i}

= EY |P_{n,4}| · \frac{−2 + (−1)^{k} + 3^{k}}{2k}

as in [7].

Putting these calculations together, we obtain

\frac{E(Y C_{k})}{EY} ∼ \frac{t}{k} + \frac{−2 + (−1)^{k} + 3^{k}}{2k} = \frac{2t − 2 + (−1)^{k} + 3^{k}}{2k} = ρ_{k}

for k ≥ 1, where t = θ_{1} + θ_{2}. A direct generalisation of this argument, applied to an ordered set of i_{1} cycles of length 1, i_{2} cycles of length 2, and so on, shows that

\frac{E (Y [C_{1}]_{i_{1}} ⋯ [C_{k}]_{i_{k}})}{EY} ∼ ∏_{j=1}^{k} ρ_{j}^{i_{j}}.

5 Synthesis

We now combine the results of Sections 2 – 4. One further piece of information is required, namely the short cycle distribution in P_{n,4}. As is well known, in P_{n,4} the variables C_{k} are asymptotically independent Poisson random variables with expectations

E_{P_{n,4}}(C_{k}) ∼ λ_{k} = \frac{3^{k}}{2k} .

Recall ρ_{k} from the previous section, and define δ_{k} by

δ_{k} = \frac{ρ_{k}}{λ_{k}} − 1 = \frac{2t − 2 + (−1)^{k}}{3^{k}} .

Then

exp (∑_{k=1}^{∞} λ_{k} δ_{k}^{2}) = exp (\frac{1}{2} ∑_{k=1}^{∞} \frac{(4t^{2} − 8t + 5) + (4t − 4)(−1)^{k}}{k 3^{k}} )

= exp (\frac{1}{2} (−(4t^{2} − 8t + 5) log (\frac{2}{3}) − (4t − 4) log (\frac{4}{3})))
= 3^{2t^{2}−2t+1/2} 2^{3/2−2t^{2}}.

But from (5) we also know that

\frac{E(Y^{2})}{(EY)^{2}} ∼ 3^{2t^{2}−2t+1/2} 2^{3/2−2t^{2}} = exp (∑_{k=1}^{∞} λ_{k} δ_{k}^{2}) .

Note further that for k ≥ 2, ρ_{k} > 0 and thus δ_{k} > −1 for all t ≥ 0. Also δ_{1} = 2t/3 − 1 which equals −1 if and only if t = 0; that is, θ_{1} = θ_{2} = 0. Therefore, by Theorem 1.4, when t > 0 we have

F̂_{n}(θ_{1}) + F̂_{n}(θ_{2}) ≈ P_{n,4},

and when t = 0 we have

F̂_{n}(θ_{1}) + F̂_{n}(θ_{2}) ≈ P′_{n,4},

as claimed.

Notice that EY^{2}/(EY)^{2} depends asymptotically only on t = θ_{1} + θ_{2}, and not on θ_{1}, θ_{2} themselves. Similarly, δ_{k} depends only on k and t, for k ≥ 1.

6 Random matchings

Recall from Section 3 that we wish to analyse

S(2k) = ∑_{(M_{1},M_{2},M_{3},M_{4})}(2θ_{1})^{κ(M_{1}∪M_{2})+κ(M_{2}∪M_{3})−2} (2θ_{2})^{κ(M_{3}∪M_{4})+κ(M_{4}∪M_{1})−2},

where M_{i} is a perfect matching on [2k] for 1 ≤ i ≤ 4. We will prove the following result, which is used in Section 3. (Throughout this section we use n in place of k.)

Theorem 6.1. With notation as above,

S(2n) ∼ \frac{π^{2} n^{2θ_{1}+2θ_{2}−2} (2n)!^{4}}{16^{n+1} Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2} n!^{4}} .

Now switch language slightly and let B, R, S, S_{1} and S_{2} be perfect matchings of [2n]. (The letters stand for Blue, Red and Silver.) Write BR for B ∪R, and so on. Also write E_{R}(·) to denote expectation over all uniformly chosen perfect matchings R of [2n]. Let m(2n) denote the number of perfect matchings on [2n], so that

m(2n) = \frac{(2n)!}{2^{n} n!}.

Now, letting B = M_{1}, R = M_{3}, S_{1} = M_{2} and S_{2} = M_{4}, we obtain

S(2n) = ∑_{B,R} ∑_{S_{1}} ∑_{S_{2}}(2θ_{1})^{κ(BS_{1})+κ(RS_{1})−2} (2θ_{2})^{κ(BS_{2})+κ(RS_{2})−2}
= m(2n)^{2} ∑_{B,R} X_{BR}(θ_{1}) X_{BR}(θ_{2}),

where

X_{BR}(θ) = E_{S}((2θ)^{κ(BS)+κ(RS)−2})

for any constant θ ≥ 0. Let μ(θ) = E_{R}(X_{BR}(θ)). (By symmetry, this does not depend on B.)

Lemma 6.1. For every θ ≥ 0,

μ(θ) ∼ \frac{π n^{2θ−1}}{4 Γ(θ + 1)^{2}} .

Proof. We have

μ(θ) = E_{R} (E_{S}((2θ)^{κ(BS)+κ(RS)−2}))
= E_{S}((2θ)^{κ(BS)−1})E_{R}((2θ)^{κ(RS)−1})
= E_{S}((2θ)^{κ(BS)−1})^{2}
∼ \frac{π n^{2θ−1}}{4 Γ(θ + 1)^{2}} .

This follows by Corollary 1.2 with c = 2θ, since adding a random silver matching to a fixed blue matching is the same as choosing a random element of P_{n,2}, where the blue matching defines the pairs of the pairing.

We will show below that X_{BR}(θ_{1})X_{BR}(θ_{2}) = μ(θ_{1})μ(θ_{2})(1 + o(1)) for almost all perfect matchings B, R. For other pairs of perfect matchings we will use this result.

Lemma 6.2. Let θ ≥ 0. For all perfect matchings B, R on [2n], we have

X_{BR}(θ) = O (n^{2θ^{2}−2θ+1/2} μ(θ)) .

Proof. Using the Cauchy-Schwarz inequality, we have

X_{BR}(θ) ≤ \sqrt{X_{BB}(θ)X_{RR}(θ)} = E_{S}((4θ^{2})^{κ(BS)−1}).

Using Lemma 6.1 and applying Corollary 1.2 with c = 4θ^{2}, we find this is asymptotically equal to

\frac{\sqrt{π} n^{(4θ^{2}−1)/2}}{2Γ(2θ^{2} + 1)} = O (n^{2θ^{2}−2θ+1/2}μ(θ)) ,

as claimed.

Given B and R, we can use a stochastic process to generate a perfect matching S on [2n], uniformly at random. We do this in such a way that we can detect whether a cycle has been formed in BS or RS. Let BR(0) = BR and start with S empty. At time t, we choose x(t) uniformly at random from the shortest cycle of BR(t − 1), and select y(t) uniformly at random from all other vertices. The edge {x(t), y(t)} is added to the silver matching S. If {x(t), y(t)} is equal to a blue (respectively red) edge of BR(t − 1) then we have created a new cycle in the evolving graph BS (respectively RS). It is possible to create a cycle in both, if and only if x(t) lies in a 2-cycle of BR(t − 1) and we choose y(t) to be its unique neighbour.

We form the graph BR(t) from BR(t − 1) by deleting x(t) and y(t); we further join the widowed B-neighbour of x(t) to the B-neighbour of y(t), unless x(t) and y(t) were neighbours of each other, and similarly for R-neighbours. This is called contracting the edge {x(t), y(t)}. This process is used by Kim and Wormald in [7].

The proof of Theorem 6.1 uses a coupling of two instances of this process. A coupling of two stochastic processes consists of a simultaneous realization of (copies of) the processes.

Given three matchings B, R_{1} and R_{2} on [2n], we define a coupling {BR_{1}(t), BR_{2}(t)}_{t=1}^{n} for the process described above. The coupling produces silver matchings (S_{1}, S_{2}) with uniform marginal probabilities. Let BR_{i}(0) = BR_{i}, for i = 1, 2 and let S_{1} = S_{2} = ∅. The transitions of the coupling are as follows: for t ≥ 1 do

(i) choose x_{i}(t) arbitrarily from the shortest cycle in BR_{i}(t − 1), for i = 1, 2,

(ii) choose y_{i}(t) uniformly at random from all remaining vertices of BR_{i}(t − 1), for i = 1, 2, subject to one condition: if BR_{1}(t−1) and BR_{2}(t−1) are non-isomorphic, then y_{1}(t) and y_{2}(t) are chosen independently, but if BR_{1}(t − 1) and BR_{2}(t − 1) are isomorphic, then

• let φ : BR_{1}(t − 1) → BR_{2}(t − 1) be a colour preserving isomorphism such

that x_{2}(t) = φ(x_{1}(t)),

• choose y_{1}(t) uniformly at random and let y_{2}(t) = φ(y_{1}(t)).

(iii) add {x_{i}(t), y_{i}(t)} to S_{i} and form BR_{i}(t) by deleting or contracting the edge {x_{i}(t), y_{i}(t)}, for i = 1, 2, as described above.

So the marginal processes BR_{i}(t) evolve independently until they become isomorphic, at which point they couple and evolve together. In particular, if BR_{1}(t) and BR_{2}(t) both are hamiltonian, they stay coupled for the rest of the process.

For convenience we define BR_{i}(t) = BR_{i}(n) for t > n.

Lemma 6.3. For every A > 0 and b > 0 there exists K = K(A, b) > 0 such that if κ(BR_{i}) ≤ A log n for i = 1, 2, then

P(κ(BR_{1}(t)) = κ(BR_{2}(t)) = 1 for some t ≤ K log n) = 1 − O(n^{−b}).

In particular, with probability 1 − O(n^{−b}), the processes couple before K log n.

Proof. For ease of notation, write

κ_{i}(t) = κ(BR_{i}(t))

for i = 1, 2 and t ≥ 0. Let

κ(t) = max {κ_{1}(t), κ_{2}(t)} .

Since x_{i}(t) is chosen from the smallest cycle of BR_{i}(t − 1), and κ_{i} decreases by 1 when x_{i}(t) and y_{i}(t) are in different components, it follows that

P(κ_{i}(t + 1) = κ_{i}(t) − 1) ≥ \frac{κ_{i}(t) − 1}{κ_{i}(t)}

for i = 1, 2. Thus, for any given BR_{1}(t) and BR_{2}(t) with κ(t) ≥ 4,

P(κ(t + 1) < κ(t)) ≥ P(κ_{1}(t + 1) = κ_{1}(t) − 1) · P(κ_{2}(t + 1) = κ_{2}(t) − 1)
≥ \frac{κ_{1}(t) − 1}{κ_{1}(t)} · \frac{κ_{2}(t) − 1}{κ_{2}(t)}
≥ \frac{9}{16}.

Moreover, κ(t) never changes by more than 1. Thus κ(t) behaves like a random walk with negative drift as long as κ(t) ≥ 4.

Let W (t) be defined by W (0) = κ(0) and W (t) = W (t − 1) + Q(t), for t ≥ 1, where the Q(t) are independent variables each with the distribution

Q(t) = \{ \begin{matrix}−1 & with probability 9/16, \\ 1 & with probability 7/16. \end{matrix}

Moreover, let N(t) be the number of times j = 0, …, t such that κ(j) ≤ 3, with N(−1) = 0. Then the process {κ(t) − 2N(t − 1)} is stochastically dominated by the process {W (t)}. (When κ(t) ≤ 3 this follows since both κ(t) and W (t) change by at most 1 per step.)

Note that EQ(t) < 0, and that we thus can find α > 0 sufficiently small such that Ee^{αQ(t)} < 1. We write Ee^{αQ(t)} = e^{−β}, where β > 0. Then

Ee^{−2αN(t)} ≤ Ee^{α(κ(t)−2N(t))} ≤ Ee^{αW (t)} = e^{ακ(0)}(Ee^{αQ(1)})^{t} = e^{ακ(0)−tβ}.  (7)

Let D = 2b/ log(16/15) and K = (αA + 2αD + b)/β. Note that D and K are both positive. Then, by (7) and our assumption κ(0) ≤ A log n, for t ≥ K log n, Markov’s inequality gives

P(N(t) ≤ D log n) ≤ e^{2αD log n}Ee^{−2αN(t)} ≤ e^{2αD log n+ακ(0)−tβ} ≤ n^{2αD+αA−βK} = n^{−b}. (8)

Let 0 ≤ T_{1} < T_{2} < … be an enumeration of the (random) times {t : κ(t) ≤ 3}. Each time we have κ(t) ≤ 3, the probability that κ(t + 2) = 1 is at least 1/16. This follows by direct calculations showing that P(κ_{i}(t + 1) = κ_{i}(t) − 1) ≥ \frac{1}{2}. Thus

P(κ(t + 1) = κ(t) − 1) ≥ \frac{1}{4}

for any BR_{1}(t), BR_{2}(t). Consequently, the events

E_{k} = {κ(t) = 1 for some t with T_{2k−1} ≤ t ≤ T_{2k+1}}, k = 1, 2, …

all have probabilities at least 1/4, also conditioned on the history up to T_{2k−1}, and consequently, for any k ≥ 0

P(κ(t) > 1 for all t ≤ T_{2k+1}) = P(⋂_{j=1}^{k} \overline{E_{j}}) ≤ (\frac{15}{16})^{k}.

Choosing k = \frac{1}{2}⌈D log n⌉ − 1, we obtain by our choice of D

P(κ(t) > 1 for all t ≤ T_{⌈D log n⌉}) ≤ (\frac{15}{16})^{\frac{1}{2}} ⌈D log n⌉ − 1 < 2n^{−b}.  (9)

Moreover, either T_{⌈D log n⌉} ≤ K log n or N(⌈K log n⌉) ≤ D log n, so combining (8) and (9) we obtain

P(κ(t) > 1 for all t ≤ K log n) ≤ P(κ(t) > 1 for all t ≤ T_{⌈D log n⌉})
+P(N(⌈K log n⌉) ≤ D log n)
< 3n^{−b}.

as claimed.

Lemma 6.4. Let θ ≥ 0 and A ≥ max {2(θ^{2} + 1), 5} be given. If B, R are perfect matchings on [2n] such that κ(BR) ≤ A log n, then

X_{BR}(θ) = μ(θ) + O(n^{−1/4}μ(θ)).

(The choice of 1/4 is arbitrary, and could be replaced by 1 − ε for any positive constant ε. We make no attempt to optimize the argument.)

Proof. This is the case α = −1/4 of the following property, which we prove for all α ≥ −3/4 by an induction, successively improving α.

H(α) : For each A ≥ max {2(θ^{2} + 1), 5}, there exists C = C(A, α, θ) such that for every n ≥ 1 and perfect matchings B and R on [2n] with κ(BR) ≤ A log n,

|X_{BR}(θ) − μ(θ)| ≤ Cn^{α}μ(θ).

Note first that Lemma 6.2 shows that H(α) holds if α ≥ 2θ^{2} − 2θ + 1/2. (This value is always nonnegative.) Now suppose that H(α) holds for some α ≥ 0; we will show that then H(α − 3/4) holds too. From this it follows that H(α′) holds for all α′ ≥ α − 3/4. This will prove the result.

Fix A ≥ max {2(θ^{2} + 1), 5} and consider three matchings B, R_{1}, R_{2} such that κ(BR_{i}) ≤ A log n for i = 1, 2. Let T = ⌊K log n⌋, where K is as in Lemma 6.3 with b = 8(θ^{4} + 1). We may assume that n is so large that T ≤ n/2 and log(n − T) ≥ \frac{1}{2} log n, since H(α−3/4) trivially is satisfied for smaller n if we choose C large enough. Consider the coupling {BR_{1}(t), BR_{2}(t)}_{t=1}^{n} described above. Define two events for the coupling:

H_{1} = {κ(BR_{1}(t)) = κ(BR_{2}(t)) = 1 for some t ≤ T } ,
H_{2} = {no cycle is created in steps 1, …, T } .

By Lemma 6.3, P(H_{1}) = 1 − O(n^{−b}). Applying the Cauchy-Schwarz inequality gives

E_{S}((2θ)^{κ(BS)+κ(R_{i}S)−2} | \overline{H_{1}}) · P(\overline{H_{1}}) ≤ \sqrt{E_{S}((4θ^{2})^{κ(BS)+κ(R_{i}S)−2})P(\overline{H_{1}})}. (10)

Note that

E_{S}((4θ^{2})^{κ(BS)+κ(R_{i}S)−2}) = X_{BR_{i}}(φ)

where φ = 2θ^{2}. Hence using Lemmas 6.1 and 6.2, we have

E_{S}((4θ^{2})^{κ(BS)+κ(R_{i}S)−2}) = O (n^{2φ^{2}−2φ+1/2}μ(φ)) = O (n^{2φ^{2}}) = O (n^{8θ^{4}}) .

Substituting this into (10) and applying Lemma 6.1 again, we find that

E_{S}((2θ)^{κ(BS)+κ(R_{i}S)−2} | \overline{H_{1}}) · P(\overline{H_{1}}) = O (n^{4θ^{4}−b/2})
= O (n^{4θ^{4}−2θ+1−b/2}μ(θ))
= O (n^{−3/4}μ(θ))  (11)

for i = 1, 2. Here the final equality follows since 4θ^{4} − 2θ + 7/4 < b/2, by choice of b.

We turn to \overline{H_{2}}. Recall that a cycle is created at step t if and only if the silver edge {x_{i}(t), y_{i}(t)} is identical to an edge of BR_{i}(t − 1), for some i ∈ {1, 2}; we call this a “bad event”. Write

\overline{H_{2}} = ⋃_{t=1}^{T} F_{t}

where F_{t} = { the first bad event occurs in step t} .

If F_{t} happens, we use the Markov property of the process. Namely, the final n − t steps of the process are exactly equivalent to starting the process with initial matchings B(t) and R_{i}(t), each on 2(n − t) points. Since

κ(BR_{i}(t)) ≤ κ(BR_{i}) + t ≤ A log n + K log n ≤ 2(A + K) log(n − t)

and 2(A + K) > A, we may apply the induction hypothesis H(α) and Lemma 6.1 to BR_{i}(t), with n replaced by n − t. This gives

X_{BR_{i}(t)}(θ) ≤ O ((n − t)^{2θ−1}) (1 + C(n − t)^{α}) = O(n^{α+2θ−1}).

Thus, since we have created at most two cycles in step t, and none before,

E((2θ)^{κ(BS_{1})+κ(R_{1}S_{1})−2} | F_{t}) ≤ max {1, (2θ)^{2}} E(X_{BR_{1}(t)}(θ) | F_{t})
= O(n^{α+2θ−1})
= O(n^{α}μ(θ)).

Moreover,

P(F_{t}) ≤ \frac{4}{2n − 2t + 1} ≤ \frac{4}{n}

and so

∑_{t=1}^{T} E((2θ)^{κ(BS_{1})+κ(R_{1}S_{1})−2} | F_{t})P(F_{t}) = O(T n^{α−1}μ(θ)) = O(n^{α−3/4}μ(θ)) (12)

and similarly for B, R_{2} and S_{2}.

Conditional on H_{1} ∩ H_{2}, we know that no cycles were created before step T, and that coupling has occurred by step T. Thus

E((2θ)^{κ(BS_{1})+κ(R_{1}S_{1})−2} | H_{1} ∩ H_{2}) = E((2θ)^{κ(BS_{2})+κ(R_{2}S_{2})−2} | H_{1} ∩ H_{2})  (13)

(where the expectation is over all choices made in the coupled process).

Combining (11), (12) we find that

X_{BR_{i}}(θ) = E((2θ)^{κ(BS_{i})+κ(R_{i}S_{i})−2} | H_{1} ∩ H_{2}) · P(H_{1} ∩ H_{2}) + O(n^{α−3/4} μ(θ))

for i = 1, 2. Moreover, the first term is the same for i = 1, 2, by (13). Therefore

X_{BR_{1}}(θ) = X_{BR_{2}}(θ) + O(n^{α−3/4}μ(θ)),  (14)

whenever κ(BR_{i}) ≤ A log n, for i = 1, 2.

Now fix perfect matchings B, R on [2n] such that κ(BR) ≤ A log n. It is well-known that P(κ(BR^{∗}) > A log n) = O(n^{−A}), where R^{∗} is a perfect matching on 2n chosen uniformly at random. (This follows from a lemma of Bernstein’s on tail estimates for sums of random variables: see [6, Remark 2.9]. For a proof when A ≥ 5 see [7, Lemma 1]: some positive constant lower bound on A is certainly required.) Thus, by Lemma 6.2 and (14),

X_{BR}(θ) − μ(θ) = E_{R^{∗}}(X_{BR}(θ) − X_{BR^{∗}}(θ))
= P(κ(BR^{∗}) > A log n) · O(n^{2θ^{2}−2θ+1/2}μ(θ))
+P(κ(BR^{∗}) ≤ A log n) · O(n^{α−3/4}μ(θ))
= O(n^{2θ^{2}−2θ+1/2−A}μ(θ) + n^{α−3/4}μ(θ))
= O(n^{α−3/4}μ(θ)),

by choice of A. This shows that H(α − 3/4) holds, completing the proof.

Before continuing, we make a note about the previous proof. We are particularly interested in the values θ ∈ \{0, \frac{1}{2}, 1\}, corresponding to random Hamilton cycles, random pseudographs arising from the pairings model, and permutation pseudographs, respectively. For these values of θ, we have 0 ≤ 2θ^{2} − 2θ + 1/2 ≤ 1/2. So applying the inductive step of the proof of Lemma 6.4 gives the conclusion immediately, which avoids the inductive framework.

The next result looks at the expected value of X_{BR}(θ_{1})X_{BR}(θ_{2}) over uniform choice of the perfect matching R, with B fixed.

Lemma 6.5. Let B be a fixed perfect matching on [2n]. With notation as above,

E_{R}(X_{BR}(θ_{1})X_{BR}(θ_{2})) = μ(θ_{1})μ(θ_{2}) (1 + o(1)).

Proof. Fix A = max {2(θ_{1}^{2} + θ_{2}^{2} + 1), 5}. Letting E_{i} be the event κ(BR_{i}) > A log(n), we know that P(E_{i}) = O(n^{−A}). Consequently, using Lemma 6.2 for E_{1} ∪ E_{2} and Lemma 6.4 for its complement \overline{E_{1}} ∩ \overline{E_{2}},

E_{R}(X_{BR}(θ_{1})X_{BR}(θ_{2})) = E_{R}(X_{BR}(θ_{1})X_{BR}(θ_{2}) | E_{1} ∪ E_{2})P(E_{1} ∪ E_{2})
+E_{R}(X_{BR}(θ_{1})X_{BR}(θ_{2}) | \overline{E_{1}} ∩ \overline{E_{2}})P(\overline{E_{1}} ∩ \overline{E_{2}})
= O(n^{2θ_{1}^{2}−2θ_{1}+1/2}μ(θ_{1})n^{2θ_{2}^{2}−2θ_{2}+1/2}μ(θ_{2})n^{−A})
+(1 − O(n^{−A}))(1 + O(n^{−1/4}))μ(θ_{1})μ(θ_{2})
= μ(θ_{1})μ(θ_{2}) (1 + o(1))

as required.

Proof of Theorem 6.1. The desired result

S(2n) ∼ \frac{π^{2} n^{2θ_{1}+2θ_{2}−2} (2n)!^{4}}{16^{n+1} Γ(θ_{1} + 1)^{2}Γ(θ_{2} + 1)^{2} n!^{4}}

follows immediately from the equation

S(2n) = m(2n)^{3} ∑_{B} E_{R}(X_{BR}(θ_{1}) X_{BR}(θ_{2})),

using Lemmas 6.1 and 6.5.

7 Further results

In this section we prove Theorem 1.2, again using the small subgraph conditioning method. The argument follows that of Sections 2 – 5 but does not require any coupling. At the end of the section we prove Theorem 1.3.

Proof of Theorem 1.2. Let θ ≥ 0 and d ≥ 3 be fixed constants. Given P ∈ P_{n,d}, we are interested in partitions (F, Q) of the pairs of P such that G(F) is a 2-regular pseudograph and G(Q) is a (d − 2)-regular pseudograph. Let

Y (P) = ∑_{(F,Q)⊢P} (2θ)^{κ(F)−1}.

We will compare the expectation and variance of Y with the expectation and variance of Z_{H}, the number of H-cycles in an element of P_{n,d}, which equals Y when θ = 0. The random variable Z_{H} was investigated by Frieze et al. in [4]. (An H-cycle is a set of n pairs which correspond to a Hamilton cycle.)

It is straightforward to show, using Lemma 1.1, that

|P_{n,d}|EY = \binom{d}{2}^{n} ∑_{F ∈P_{n,2}}(2θ)^{κ(F)−1} |P_{n,d−2}|

∼ d^{n}(d − 1)^{n} n!\frac{n^{θ−1}}{2Γ(θ + 1)} |P_{n,d−2}|.

Putting θ = 0 here gives an equation for |P_{n,d}|EZ_{H}, from which we conclude that

EY ∼ \frac{n^{θ}}{Γ(θ + 1)} EZ_{H}.  (15)

The variance calculation is simpler than that of Section 3, since no coupling argument is required. We calculate

|P_{n,d}|E(Y^{2}) = ∑_{P ∈P_{n,d}} ∑_{(F_{1},Q_{1})⊢P} ∑_{(F_{2},Q_{2})⊢P} (2θ)^{κ(F_{1})+κ(F_{2})−2}.

First consider F_{1} ∩ F_{2}. Colour the corresponding edges in G(P) gold. We imitate the argument of Section 3 for the golden edges, but argue more directly for the remaining edges. As in Section 3, say that a vertex in G(P) has type A, B or C if it is incident with 1, 2 or 0 golden edges, respectively. The golden edges form a union of some paths and some closed cycles. The endpoints of these paths have type A, while the interior vertices of the paths and cycles have type B. Moreover, each vertex of type A is the endpoint of a golden path, and each vertex of type B lies on a golden path or cycle. Suppose that there are a = 2k type A vertices, b type B vertices and c = n − 2k − b type C vertices. Then again there are

\frac{n!}{(2k)! b! c!}

ways to assign types to these vertices. Instead of the connection scheme used in Section 3, we just choose a perfect matching of the type A vertices, to determine the endpoints of each golden path. There are

\frac{(2k)!}{2^{k} k!}

such matchings. Now add the type B vertices onto the golden paths and cycles. Each golden cycle is a cycle in F_{1} and in F_{2}. Therefore it should contribute weight 4θ^{2}. Instead, as in Section 3, we give each golden cycle weight 4θ^{2} if it has length greater than 2, and weight 2θ^{2} otherwise. This underweights each cycle of length 1 or 2 by a factor of 2, but this will be corrected below. Using these weights, the contribution from adding all the type B vertices is

b!\binom{k + b + 2θ^{2} − 1}{b} ∼ (\frac{k + b}{k})^{2θ^{2}−1} \frac{(k + b)!}{k!}.

(This assumes that k → ∞, as in Section 3.)

Now choose which points in each bucket belong to pairs in F_{1} and F_{2}. For each vertex of type A there are d choices for the point in F_{1} ∩ F_{2}, d − 1 for the other point in F_{1} and d − 2 for the other point in F_{2}. For each vertex of type C we choose the points in F_{1} in \binom{d}{2} ways and then the points in F_{2} in \binom{d−2}{2} ways. For each vertex of type B there are \binom{d}{2} ways to choose the two points in F_{1} ∩ F_{2}. The position of this vertex on a golden path or cycle of G(P) has already been determined. Multiply by 2 to count the number of ways to wire these points to their neighbours in the path or cycle. This factor d(d − 1) for each type B vertex gives a factor 2 too much for each golden cycle of length 1 or 2. We have already compensated for this factor in the preceding step. Thus the total factor is

(d(d − 1)(d − 2))^{2k} (d(d − 1))^{b} (\binom{d}{2}\binom{d − 2}{2})^{c} = 2^{−2c} d^{n}(d − 1)^{n}(d − 2)^{2k+c}(d − 3)^{c}.

At this stage, F_{1} ∩F_{2} is complete determined. We now specify the remaining pairs in F_{1}, F_{2}, as well as the pairs in Q_{1} ∩ Q_{2}. To specify the remaining pairs of F_{1}, delete each golden cycle and contract each golden path to a single vertex. The number of vertices left is n − (2k + b) + k = k + c, and each remaining vertex corresponds to a bucket with two points from F_{1} ∩ Q_{2} specified. (For vertices which correspond to shrunken paths, each endpoint of the path contributes one of these points.) Choose a perfect matching on these 2(k + c) points with the usual weighting: these determine the remaining pairs of F_{1}. Therefore the contribution from completing F_{1} is

∑_{F ∈P_{k+c,2}}(2θ)^{κ(F)−1} ∼ \frac{2^{k+c} (k + c)!}{2Γ(θ + 1)}(k + c)^{θ−1},

using Lemma 1.1 and assuming that k → ∞. Completing F_{2} contributes the same factor. Finally, to specify the pairs of Q_{1} ∩ Q_{2} we need only form a perfect matching of the remaining the remaining dn − 6k − 2b − 4c = (d − 4)n + 2k + 2b points. The number of ways to do this is

|P_{(d−4)n+2k+2b,1}| = \frac{((d − 4)n + 2k + 2b)!}{2^{(d/2−2)n+k+b} ((d/2 − 2)n + k + b)!}.

Combining all these factors gives

|P_{n,d}|E(Y^{2}) ∼ ∑_{k} ∑_{b} (\frac{k + b}{k})^{2θ^{2}} \frac{(k + c)^{2θ}}{Γ(θ + 1)^{2}} t(k, b),  (16)

where

t(k, b) = \frac{n! k (k + b)! (k + c)!^{2} d^{n}(d − 1)^{n}(d − 2)^{2k+c} (d − 3)^{c}}{4 k!^{2} b! c! (k + b) (k + c)^{2}}

×\frac{((d − 4)n + 2k + 2b)!}{2^{(d/2−2)n+b} ((d/2 − 2)n + k + b)!}

does not depend on θ. The case θ = 0 was analysed in [4] (for d = 3, which is simpler since then c = 0, see [9]). The method of [4] is similar but the notation differs: denoting their k and a by k′ and a′, we have a′ = k (the number of paths in F_{1} ∩ F_{2}) and k′ = k + b (the number of edges in F_{1} ∩ F_{2}). With these substitutions, (16) with θ = 0 is equivalent to [4, (14)]. It is shown in [4] that only terms with k′/n ∼ κ_{0} = 2/d and a′/n ∼ α_{0} = 2(d − 2)/d(d − 1) contribute significantly to the sum. It follows that only terms with k ∼ α_{0}n and b ∼ (κ_{0} − α_{0})n contribute significantly to the sum in (16). Therefore

|P_{n,d}|E(Y^{2}) ∼ (\frac{κ_{0}}{α_{0}} )^{2θ^{2}} \frac{((1 − κ_{0})n)^{2θ}}{Γ(θ + 1)^{2}} ∑_{k} ∑_{b} t(k, b)

∼ (\frac{κ_{0}}{α_{0}} )^{2θ^{2}} \frac{((1 − κ_{0})n)^{2θ}}{Γ(θ + 1)^{2}} |P_{n,d}|E(Z_{H}^{2})

= (\frac{d − 1}{d − 2})^{2θ^{2}} (\frac{d − 2}{d})^{2θ} \frac{n^{2θ}}{Γ(θ + 1)^{2}} |P_{n,d}|E(Z_{H}^{2}).

Combining these with (15) we finally find that

\frac{E(Y^{2})}{(EY)^{2}} ∼ (\frac{d − 1}{d − 2})^{2θ^{2}} (\frac{d − 2}{d})^{2θ} \frac{E(Z_{H}^{2})}{(EZ_{H})^{2}} ∼ (\frac{d − 1}{d − 2})^{2θ^{2}} (\frac{d − 2}{d})^{2θ−1} .

The second asymptotic equality follows since E(Z_{H}^{2})/(EZ_{H})^{2} ∼ d/(d − 2), as shown in [4].

Finally, we must calculate the effect of short cycles. The approach is very similar to that used by Robalewska in [8, Lemma 1]. The case C ∩ F = C is handled as in Section 4, and gives a contribution of

\frac{θ}{k} |P_{n,d}|EY.

Next suppose that C ∩ F = ∅. Then divide by 2 to undirect the cycle, if k ≥ 3. There are ((d − 2)(d − 3))^{k} ways to wire C into the specified points of the subpairing Q, if k ≥ 3, and ((d − 2)(d − 3))^{k}/2 ways if k = 1, 2. (The net effect of this is to multiply by ((d − 2)(d − 3))^{k}/2 for all k.) There are asymptotically

\frac{|P_{n,d−2}|}{(n(d − 2))^{k}}

ways to complete the pairing Q, since k pairs are already specified. Finally the contribution from all possible choices of F is 2^{n} n! n^{θ−1}/2Γ(θ + 1), by Lemma 1.1. Hence the contribution from case (ii) is

\binom{d}{2}^{n} · \frac{n^{k}}{k} · \frac{((d − 2)(d − 3))^{k}}{2} · \frac{|P_{n,d−2}|}{(n(d − 2))^{k}} · \frac{2^{n} n! n^{θ−1}}{2Γ(θ + 1)} = \frac{(d − 3)^{k}}{2k} |P_{n,d}|EY.

Finally, suppose that C ∩ F is the union of i disjoint paths. Suppose that these paths contain k − r vertices, so that there are r isolated vertices in C ∩ F. Let N_{ir} be the number of ways to ensure that C ∩ F has this form, starting without the vertices of C specified. Then Robalewska [8] shows that

N_{ir} ∼ n^{k}[x^{k}y^{i}z^{r}] (−\frac{1}{2}log((1 − x)(1 − xz) − x^{2}y)) .

There are 2^{k−r} ways to wire C ∩ F into the specified points of the subpairing F. The contribution from extending C ∩ F to F in all possible ways is

∑_{F ∈P_{n−(k−(i+r)),2}}(2θ)^{κ(F)−1} ∼ \frac{2^{n−(k−(i+r))}n!n^{θ−1}}{2 n^{k−(i+r)} Γ(θ + 1)},

as in (6). Next, there are

(d − 2)^{2i+r}(d − 3)^{r}

ways to wire C ∩ Q into the specified points of the subpairing Q. Then the number of ways to complete C ∩ Q to Q is asymptotically equal to

\frac{|P_{n,d−2}|}{(n(d − 2))^{r+i}} .

Hence the total contribution from case (iii) is

|P_{n,d}|EY ∑_{i≥1} ∑_{r≥0}[x^{k}y^{i}z^{r}] (−\frac{1}{2}log((1 − x)(1 − xz) − x^{2}y)) · (2(d − 2))^{i}(d − 3)^{r}.

Putting this together (and mirroring the calculations in [8, Lemma 1]), noting that only the first term depends on θ, we obtain

\frac{E(Y C_{k})}{EY} = \frac{θ}{k} + \frac{(d − 3)^{k}}{2k}

+ ∑_{i≥1} ∑_{r≥0}[x^{k}y^{i}z^{r}] (−\frac{1}{2}log((1 − x)(1 − xz) − x^{2}y)) · (2(d − 2))^{i}(d − 3)^{r}

= \frac{2θ − 1 + (−1)^{k} + (d − 1)^{k}}{2k}
= ρ_{k}.

It is routine to verify that Y behaves well under joint short cycle distributions.

As is well-known, the distribution of k-cycles in P_{n,d} is asymptotically Poisson with mean

λ_{k} = \frac{(d − 1)^{k}}{2k} .

Define δ_{k} for k ≥ 1 by

δ_{k} = \frac{ρ_{k}}{λ_{k}} − 1 = \frac{2θ − 1 + (−1)^{k}}{(d − 1)^{k}} .

Then

exp (∑_{k≥1} λ_{k}δ_{k}^{2}) = exp (∑_{k≥1} \frac{2θ^{2} − 2θ + 1 + (2θ − 1)(−1)^{k}}{k(d − 1)^{k}} )

= (\frac{d − 1}{d − 2})^{2θ^{2}−2θ+1} (\frac{d − 1}{d})^{2θ−1}
= \frac{E(Y^{2})}{(EY)^{2}}.

Therefore, using Theorem 1.4 we have

P_{n,d−2} + F̂_{n}(θ) ≈ P_{n,d}

when θ > 0 or d > 3, and

P_{n,1} + F̂_{n}(0) ≈ P′_{n,3}

(since here ρ_{1} = 0 and δ_{1} = −1.) This completes the proof.

Proof of Theorem 1.3. Combine the graphs in a suitable order using Theorems 1.1 and 1.2, together with known results for sums of G_{n,d}^{∗} as in the proof of [5, Theorem 9.43] or [14, Corollary 4.17].

References

[1] Bollobás, B. (1985) Random graphs, Academic Press.

[2] Friedman, J. (1991) On the second eigenvalue and random walks in random dregular graphs, Combinatorica 11 331–362.

[3] Frieze, A. (2001) Hamilton cycles in the union of random permutations, Random Structures Algorithms 18 83–94.

[4] Frieze, A., Jerrum. M., Molloy, M., Robinson, R., and Wormald, N. (1996) Generating and counting Hamilton cycles in random regular graphs, J. Algorithms 21 176–198.

[5] Janson, J. (1995) Random regular graphs: asymptotic distributions and contiguity, Comb. Prob. Comp. 4 369–405.

[6] Janson, S., Łuczak,T. and Ruciński, A. (2000) Random Graphs, John Wiley and Sons.

[7] Kim, J. H. and Wormald, N. C. (2001) Random matchings which induce Hamilton cycles, and hamiltonian decompositions of random regular graphs, J. Combin. Theory Ser. B 81 20–44.

[8] Robalewska, H. 2-factors in random regular graphs, J. Graph Theory 23 215–224.

[9] Robinson, R. W. and Wormald, N. C. (1992) Almost all cubic graphs are hamiltonian, Random Structures Algorithms 3 117–125.

[10] Robinson, R. W. and Wormald, N. C. (1994) Almost all regular graphs are hamiltonian, Random Structures Algorithms 5 363–374.

[11] Tavaré, S. and Ewens, W. J. (1995) The Ewens Sampling Formula, Manuscript,

available from http://www-hto.usc.edu/papers/abstracts/esfrep.html.

[12] Tavaré, S. and Ewens, W. J. (1997) Multivariate Ewens Distribution, appeared as Chapter 41 of Johnson, N. L., Kotz, S. and Balakrishnan, N., Discrete Multivariate Distributions, Wiley.

[13] Wilf, H. S. (1990) generatingfunctionology, Academic Press.

[14] Wormald, N. C. (1999) Models of random regular graphs. In Lamb, J. D. and Preece, D. A. (editors) Surveys in Combinatorics 1999, LMS Lecture Note Series 267 239–298. Cambridge University Press.