Introduction
Graph-structured representations offer a flexible way to model complex relationships and are therefore central to a broad spectrum of applications, ranging from semantic knowledge representation and molecular analysis to computer vision. In many of these settings, graphs rarely coincide exactly: they may differ in size, labelling, connectivity, or local structure while still encoding related information. This motivates the study of graph similarity, which replaces the yes-or-no notion of graph isomorphism with a graded measure of structural resemblance. By enabling meaningful comparisons between imperfect or partially aligned graphs, similarity measures provide a foundation for important learning tasks over graph data, including graph classification, clustering, pattern discovery, and anomaly detection.
Among the various approaches to quantify similarity, graph overlap is a widely used and intuitive measure. Rather than requiring an exact structural correspondence, graph overlap measures the extent to which the two graphs share common structural elements, such as vertices, edges, or substructures. This makes graph overlap particularly suitable for applications in which graphs may be only partially similar or may contain noise, missing information, or additional structures.
We quantify the similarity between two graphs by the number of shared edges they have. More precisely, we consider two graphs defined on the same vertex set.
Definition 1.1 (Graph overlap). Let G 1 G_1 G 1 and G 2 G_2 G 2 be two graphs with a common vertex set V V V , where n = ∣ V ∣ n = |V| n = ∣ V ∣ . For a permutation π ∈ S n \pi\in\mathfrak{S}_n π ∈ S n of [ n ] = { 1 , … , n } [n] = \{1,\ldots,n\} [ n ] = { 1 , … , n } , the graph overlap of G 1 G_1 G 1 and G 2 G_2 G 2 under π \pi π is defined by
Ov π ( G 1 , G 2 ) = ∣ π ( E ( G 1 ) ) ∩ E ( G 2 ) ∣ . \operatorname{Ov}_{\pi}(G_1,G_2) = \left|\pi(E(G_1)) \cap E(G_2)\right|. Ov π ( G 1 , G 2 ) = ∣ π ( E ( G 1 )) ∩ E ( G 2 ) ∣ . The maximum overlap is then given by
M n = max π ∈ S n Ov π ( G 1 , G 2 ) . (1) M_n = \max_{\pi\in\mathfrak{S}_n} \operatorname{Ov}_{\pi}(G_1,G_2). \tag*{(1)} M n = π ∈ S n max Ov π ( G 1 , G 2 ) . (1)
The quantity M n M_n M n is closely related to the graph edit distance (GED) [16 ] . In general, the GED between two graphs, possibly equipped with vertex and edge labels, is defined as the minimum cost of an edit sequence that transforms one graph into a graph isomorphic to the other. The allowed edit operations may include inserting, deleting, or substituting vertices and edges, with each operation assigned a non-negative cost [8 ] .
For unlabelled graphs on the same vertex set, when only edge insertions and deletions are permitted, and every operation has unit cost, the edge-based GED is given by
GED E ( G 1 , G 2 ) = min π ∈ S n ∣ π ( E ( G 1 ) ) △ E ( G 2 ) ∣ = ∣ E ( G 1 ) ∣ + ∣ E ( G 2 ) ∣ − 2 M n . (2) \operatorname{GED}_{E}(G_1,G_2) = \min_{\pi\in\mathfrak{S}_n} \left|\pi(E(G_1)) \triangle E(G_2)\right| = |E(G_1)| + |E(G_2)| - 2M_n. \tag*{(2)} GED E ( G 1 , G 2 ) = π ∈ S n min ∣ π ( E ( G 1 )) △ E ( G 2 ) ∣ = ∣ E ( G 1 ) ∣ + ∣ E ( G 2 ) ∣ − 2 M n . (2)
In this paper, we assume that G 1 G_1 G 1 and G 2 G_2 G 2 are independent copies of the same graph distribution, so that M n M_n M n represents a notion of self-similarity within the same graph ensemble. Both graph overlap and edit distance have been investigated in the setting of independent Erdős–Rényi random graphs.
Related work Comparisons of independent realisations of the same random graph model have been investigated from several perspectives. Hartle et al. [9 ] introduced the notion of within-ensemble graph distance , studying the typical distance between two independent samples from a common graph ensemble. Their analysis covers several random graph models, including Erdős–Rényi graphs, random geometric graphs, Watts–Strogatz networks, configuration models, and preferential attachment networks, using a variety of graph distance measures. This provides a general framework for understanding how structural variability within an ensemble is reflected by different notions of graph similarity.
From a mathematical perspective, Bollobás and Riordan [2 , 1 ] investigated metrics on sparse graphs, including edit and cut distances, with particular attention to random graphs having a linear number of edges. In the Erdős–Rényi model G ( n , p ) \mathcal{G}(n,p) G ( n , p ) with p = c / n p = c/n p = c / n , their results show that, for fixed c > 1 c > 1 c > 1 , two independent realisations have an edit distance bounded below by a positive constant times n n n with high probability. Their framework also addresses more general inhomogeneous sparse random graph models. More recently, Ding, Du, and Gong [6 ] studied the maximum overlap between two independent Erdős–Rényi graphs in denser regimes. For p = n − α p = n^{-\alpha} p = n − α with α ∈ ( 1 / 2 , 1 ) \alpha\in(1/2,1) α ∈ ( 1/2 , 1 ) , they established that
M n ∼ n 2 α − 1 M_n \sim\frac{n}{2\alpha- 1} M n ∼ 2 α − 1 n
with high probability, and provided a polynomial-time approximation scheme achieving an arbitrarily close multiplicative approximation to the optimum. This shows that optimising the vertex correspondence can produce a linear overlap even when the two graphs are independently generated. The algorithmic aspects of this problem were further investigated by Du, Gong, and Huang [7 ] , who identified a phase transition around
p c = log n n . p_c = \sqrt{\frac{\log n}{n}}. p c = n log n .
They established polynomial-time approximation schemes in the sparse regime and identified algorithmic limitations in the dense regime, including hardness results for online and greedy local iterative algorithms. Their overlap analysis also provides evidence of a broader statistical-computational gap, although the hardness of arbitrary polynomial-time algorithms remains open.
In this paper, we investigate the maximum overlap within the ensemble of uniform random d d d -regular graphs. Unlike Erdős–Rényi graphs, these graphs satisfy a hard degree constraint, which introduces dependencies between their edges. Moreover, for fixed d ≥ 3 d \ge3 d ≥ 3 , the presence of Hamilton cycles provides a natural linear baseline for the overlap. Our aim is to determine not only this leading-order behaviour, but also the order of the additional overlap achievable by optimising over vertex permutations.
Labelled versus unlabelled overlap
We focus on the set G n , d \mathcal{G}_{n,d} G n , d of simple d d d -regular graphs on [ n ] [n] [ n ] , where d d d is fixed and n d nd n d is even. We denote by U n , d \mathcal{U}_{n,d} U n , d the uniform probability measure on G n , d \mathcal{G}_{n,d} G n , d . Throughout the paper, G 1 G_1 G 1 and G 2 G_2 G 2 are independent samples from U n , d \mathcal{U}_{n,d} U n , d , and all asymptotic statements are understood along admissible values of n n n .
To illustrate the effect of optimising over vertex permutations, we first consider the overlap under a fixed labelling. Let
X n : = ∣ E ( G 1 ) ∩ E ( G 2 ) ∣ X_n := |E(G_1) \cap E(G_2)| X n := ∣ E ( G 1 ) ∩ E ( G 2 ) ∣
be the number of common edges. Since each unordered pair of vertices is an edge of a uniform d d d -regular graph with probability d / ( n − 1 ) d/(n-1) d / ( n − 1 ) , independence gives
E [ X n ] = ( n 2 ) ( d n − 1 ) 2 = n d 2 2 ( n − 1 ) = d 2 2 + o ( 1 ) . \mathbb{E}[X_n] = \binom{n}{2}\left(\frac{d}{n-1}\right)^2 = \frac{nd^2}{2(n-1)} = \frac{d^2}{2} + o(1). E [ X n ] = ( 2 n ) ( n − 1 d ) 2 = 2 ( n − 1 ) n d 2 = 2 d 2 + o ( 1 ) .
In fact, using standard estimates for random regular graphs (see, e.g., [12 Chapter 9] ), a factorial-moment argument shows that, for every fixed d d d , X n X_n X n converges in distribution to a Poisson random variable with mean d 2 / 2 d^2/2 d 2 /2 . Thus, the overlap under a fixed labelling remains of constant order as n n n grows, and in particular vanishes with a probability bounded away from zero.
Allowing vertex relabelings changes the picture. For any two graphs G 1 G_1 G 1 and G 2 G_2 G 2 on the same vertex set, consider a uniformly random permutation π ∈ S n \pi\in S_n π ∈ S n . Since the image of each fixed edge is uniformly distributed over the ( n 2 ) \binom{n}{2} ( 2 n ) unordered vertex pairs, we have
E π [ Ov π ( G 1 , G 2 ) ] = ∣ E ( G 1 ) ∣ ∣ E ( G 2 ) ∣ ( n 2 ) . \mathbb{E}_{\pi}[\operatorname{Ov}_{\pi}(G_1,G_2)] = \frac{|E(G_1)||E(G_2)|}{\binom{n}{2}}. E π [ Ov π ( G 1 , G 2 )] = ( 2 n ) ∣ E ( G 1 ) ∣∣ E ( G 2 ) ∣ .
Consequently, at least one permutation achieves an overlap no smaller than this average. Since every d d d -regular graph has exactly n d / 2 nd/2 n d /2 edges, we obtain the deterministic bound
M n ≥ ⌈ n d 2 2 ( n − 1 ) ⌉ . M_n \ge\left\lceil\frac{nd^2}{2(n-1)} \right\rceil. M n ≥ ⌈ 2 ( n − 1 ) n d 2 ⌉ .
Although this elementary argument only yields a constant lower bound, optimising over vertex permutations has a much stronger effect: as we show below, the maximum overlap between two independent random d d d -regular graphs is typically of linear order in n n n .
Main results
Our objective is to characterise the maximum overlap between two independent uniform random d d d -regular graphs, for each fixed d ≥ 1 d \ge1 d ≥ 1 . We will show that the behaviour changes significantly between the regimes d = 1 d = 1 d = 1 , d = 2 d = 2 d = 2 , and d ≥ 3 d \ge3 d ≥ 3 as summarised in the following table:
Table 1.
When d = 1 d = 1 d = 1 , both graphs are perfect matchings, and any two perfect matchings on the same vertex set are isomorphic. Consequently, all n / 2 n/2 n /2 edges can be aligned, yielding M n = n / 2 M_n = n/2 M n = n /2 and G E D E ( G 1 , G 2 ) = 0 \mathrm{GED}_E(G_1,G_2) = 0 GED E ( G 1 , G 2 ) = 0 deterministically.
The case d = 2 d = 2 d = 2 is more interesting. Here, each graph is a disjoint union of cycles, and although two independent realisations are typically not isomorphic, their cycle decompositions can be aligned so that only a logarithmic number of edges remain unmatched.
Theorem 1.2 (Overlap in degree two). Let d = 2 d = 2 d = 2 . Then
n − M n log n → P 1. \frac{n - M_n}{\log n} \xrightarrow{\mathbb{P}} 1. log n n − M n P 1. More precisely, with c ( G ) c(G) c ( G ) denoting the number of cycles of G G G ,
M n = n − c ( G 1 ) − c ( G 2 ) + O P ( 1 ) . M_n = n - c(G_1) - c(G_2) + O_{\mathbb{P}}(1). M n = n − c ( G 1 ) − c ( G 2 ) + O P ( 1 ) .
Since both graphs have exactly n n n edges, this also implies that G E D E ( G 1 , G 2 ) = ( 2 + o P ( 1 ) ) log n \mathrm{GED}_E(G_1,G_2) = (2 + o_{\mathbb{P}}(1))\log n GED E ( G 1 , G 2 ) = ( 2 + o P ( 1 )) log n . Thus, unlike the case d = 1 d = 1 d = 1 , two independent random 2-regular graphs are typically not isomorphic, but they can be made almost identical by an appropriate relabelling, with only a logarithmic number of edge modifications.
For every fixed d ≥ 3 d \ge3 d ≥ 3 , the behaviour is fundamentally different. A classical result of Robinson and Wormald [15 ] guarantees that a uniform random d d d -regular graph is Hamiltonian with high probability. Consequently, two independent realisations contain Hamilton cycles that can be perfectly aligned through a suitable vertex permutation, yielding M n ≥ n M_n \ge n M n ≥ n with high probability. On the other hand, a first-moment argument shows that the maximum overlap cannot exceed ( 1 + ε ) n (1 + \varepsilon)n ( 1 + ε ) n with high probability for any fixed ε > 0 \varepsilon> 0 ε > 0 .
Theorem 1.3 (First-order overlap). For every fixed d ≥ 3 d \ge3 d ≥ 3 and every ε > 0 \varepsilon> 0 ε > 0 ,
lim n → ∞ P ( ∣ M n n − 1 ∣ ≤ ε ) = 1. \lim_{n \to\infty} \mathbb{P}\left(\left|\frac{M_n}{n} - 1\right| \le\varepsilon\right) = 1. n → ∞ lim P ( n M n − 1 ≤ ε ) = 1.
This determines the leading-order behaviour of the maximum overlap. The next question is whether an appropriate relabelling can systematically improve upon the overlap of n n n edges provided by aligning two Hamilton cycles. To quantify this improvement, we introduce the surplus overlap
S n : = M n − n . S_n := M_n - n. S n := M n − n .
Our main results identify the correct asymptotic order of this surplus and give explicit degree-dependent constants. Set
a d : = log ( d − 1 ) + d − 2 2 log ( d − 2 d ) , b d : = d log ( d − 1 ) − ( d − 2 ) log ( d + 1 ) . a_d := \log(d-1) + \frac{d-2}{2}\log\left(\frac{d-2}{d}\right), \qquad b_d := d\log(d-1) - (d-2)\log(d+1). a d := log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) , b d := d log ( d − 1 ) − ( d − 2 ) log ( d + 1 ) .
We first establish an upper bound showing that, for any fixed d ≥ 3 d \ge3 d ≥ 3 , the surplus cannot exceed order n / log n n/\log n n / log n with high probability.
Theorem 1.4 (Second-order upper bound). For every fixed d ≥ 3 d \ge3 d ≥ 3 and every ε > 0 \varepsilon> 0 ε > 0 ,
lim n → ∞ P ( S n ≤ ( b d + ε ) n log n ) = 1. \lim_{n\to\infty} \mathbb{P}\left(S_n \le(b_d+\varepsilon)\frac{n}{\log n}\right)=1. n → ∞ lim P ( S n ≤ ( b d + ε ) log n n ) = 1.
The proof again uses a first-moment argument, but now after a structural reduction. Any overlap of size n + s n+s n + s contains a common subgraph (a core ) of minimum degree at least two and graph excess exactly s s s . Counting these common cores and optimising over their number of vertices gives the constant b d b_d b d ; the first moment is maximised by cores occupying asymptotically d / ( d + 1 ) d/(d+1) d / ( d + 1 ) of the vertices.
For the lower bound, we first fix a Hamilton cycle in each graph and consider a permutation that perfectly aligns the two cycles, yielding an overlap of at least n n n edges. Cyclically rotating this permutation preserves the alignment of all n n n Hamiltonian edges, while changing the correspondence between the remaining edges. We exploit these n n n possible rotations to search for additional overlaps beyond the Hamiltonian baseline. Using contiguity arguments, the residual edges can be analysed through a suitable random matching model. We then identify local configurations witnessing additional overlaps and control the dependencies among different rotations by selecting witnesses with distinct cyclic lengths. This yields a surplus of order log n / log log n \log n/\log\log n log n / log log n with high probability.
To reach the larger scale n / log n n/\log n n / log n , we need to pass from a single Hamilton cycle to a spanning collection of cycles of the same logarithmic length k k k .
Theorem 1.5 (Second-order lower bound). For every fixed d ≥ 3 d \ge3 d ≥ 3 and every ε > 0 \varepsilon> 0 ε > 0 ,
lim n → ∞ P ( S n ≥ ( a d − ε ) n log n ) = 1. \lim_{n\to\infty} \mathbb{P}\left(S_n \ge(a_d-\varepsilon)\frac{n}{\log n}\right)=1. n → ∞ lim P ( S n ≥ ( a d − ε ) log n n ) = 1.
In this case, we use a different probabilistic mechanism. At the correct length scale k k k , the expected number of realised k k k -cycle factors is sub-exponential in n n n , which allows us to prove two properties simultaneously for every such factor. We can then choose the spanning factor after examining the graph and, consequently, align groups of cycles as stars. This procedure gains one additional common edge per factor cycle, asymptotically, and at the same time, no cycle-factor contiguity argument is needed.
Together, the bounds establish the correct asymptotic order of the surplus, S n = Θ P ( n / log n ) S_n = \Theta_{\mathbb{P}}(n/\log n) S n = Θ P ( n / log n ) . Figure 1 depicts the distance between the upper and lower constants. For d = 3 d=3 d = 3 , they are
Figure 1. Lower- and upper-bound constants a d a_d a d and b d b_d b d in the second-order overlap bounds in Theorems 1.4 -1.5 , for two independent random d d d -regular graphs.
a 3 = 1 2 log 4 3 ≈ 0.14384 , b 3 = log 2 ≈ 0.69315. a_3 = \frac{1}{2}\log\frac{4}{3} \approx0.14384, \qquad b_3 = \log2 \approx0.69315. a 3 = 2 1 log 3 4 ≈ 0.14384 , b 3 = log 2 ≈ 0.69315.
More generally, a d = log d − 1 + O ( d − 2 ) a_d = \log d - 1 + O(d^{-2}) a d = log d − 1 + O ( d − 2 ) while b d = 2 log d − 2 + 2 / d + O ( d − 2 ) b_d = 2\log d - 2 + 2/d + O(d^{-2}) b d = 2 log d − 2 + 2/ d + O ( d − 2 ) , so the ratio of the coefficients tends to 2, as d d d grows.
Further results
As a by-product, our analysis also yields an independent result concerning the maximum overlap between unions of random perfect matchings under cyclic shifts.
Theorem 1.6 (Overlap of independent perfect matchings). Fix positive integers q 1 , q 2 q_1,q_2 q 1 , q 2 and let n n n be even. For i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } , let M i , 1 , … , M i , q i \mathcal{M}_{i,1},\ldots,\mathcal{M}_{i,q_i} M i , 1 , … , M i , q i be mutually independent uniform perfect matchings on Z n \mathbb{Z}_n Z n , with all matchings independent across the two families, and define
R i = ⋃ j = 1 q i M i , j . R_i = \bigcup_{j=1}^{q_i} \mathcal{M}_{i,j}. R i = j = 1 ⋃ q i M i , j . Then, for every ε > 0 \varepsilon> 0 ε > 0 ,
lim n → ∞ P ( ∣ max s ∈ Z n ∣ ρ s ( R 1 ) ∩ R 2 ∣ log n / log log n − 1 ∣ ≤ ε ) = 1 , \lim_{n\to\infty} \mathbb{P}\left(\left|\frac{\max_{s\in\mathbb{Z}_n}|\rho_s(R_1)\cap R_2|}{\log n/\log\log n}-1\right|\leq\varepsilon\right)=1, n → ∞ lim P ( log n / log log n max s ∈ Z n ∣ ρ s ( R 1 ) ∩ R 2 ∣ − 1 ≤ ε ) = 1 , where ρ s ( x ) = x + s ( m o d n ) \rho_s(x)=x+s\pmod n ρ s ( x ) = x + s ( mod n ) denotes the cyclic shift by s s s .
This result identifies the precise asymptotic scale of the largest overlap achievable through cyclic shifts of unions of independent random matching. It also provides the probabilistic ingredient underlying our analysis of rotations of aligned Hamilton cycles. Its proof is deferred to Section C in the appendix.
A further ingredient in our second-order lower bound is the existence of k k k -cycle factors in random regular graphs, where k k k is of order log n \log n log n . Kahn, Lubetzky, and Wormald [13 ] established the sharp threshold in random cubic graphs and explicitly state that their proof extends, with very few modifications, to every fixed degree d ≥ 3 d\geq3 d ≥ 3 . In § 2 , we extract the degree-dependent threshold constant from the first moment.
Organisation of the paper
Section 2 collects model definition, Hamilton-cycle contiguity, and the cycle-factor threshold used later. Section 3 contains the proofs for d = 1 , 2 d=1,2 d = 1 , 2 and first-order overlap estimates for fixed degree d ≥ 3 d\geq3 d ≥ 3 . Section 4 proves the second-order upper bound by reducing a large overlap to a common minimum-degree-two core. Section 5 studies the weaker but more explicit surplus obtainable by rotations of aligned Hamilton cycles, using a planted-model contiguity argument. Section 6 proves the matching-order lower bound from logarithmic cycle factors by an argument working uniformly over all cycle factors and a deterministic star construction. We conclude with a discussion of the remaining constant gap and related open questions.
Preliminaries
We use the notation G n , d \mathcal{G}_{n,d} G n , d and U n , d \mathcal{U}_{n,d} U n , d introduced in § 1 . Unless otherwise specified, d d d is fixed, and all asymptotic statements are understood along admissible values of n n n , namely those for which n d nd n d is even. For two independent samples G 1 , G 2 ∼ U n , d G_1,G_2 \sim\mathcal{U}_{n,d} G 1 , G 2 ∼ U n , d , recall that
M n = max π ∈ S n ∣ π ( E ( G 1 ) ) ∩ E ( G 2 ) ∣ . M_n = \max_{\pi\in\mathfrak{S}_n} \left|\pi(E(G_1)) \cap E(G_2)\right|. M n = π ∈ S n max ∣ π ( E ( G 1 )) ∩ E ( G 2 ) ∣ .
Note that, in what follows, all logarithms are natural.
The configuration model
We recall the configuration model, which provides a convenient representation of uniform random regular graphs. In the d d d -regular configuration model, each vertex is assigned d d d distinguishable half-edges, and a uniform perfect matching of the d n dn d n half-edges is sampled. The resulting graph is a d d d -regular multigraph, possibly containing loops or multiple edges.
The probability that t t t prescribed disjoint pairs of half-edges occur in the uniform matching is
∏ j = 0 t − 1 1 d n − 2 j − 1 . (3) \prod_{j=0}^{t-1} \frac{1}{dn-2j-1}. \tag*{(3)} j = 0 ∏ t − 1 d n − 2 j − 1 1 . (3)
For fixed d d d , the probability that the resulting multigraph is simple satisfies the following classical asymptotic estimate (see [11 ] ):
P ( G n , d C M is simple ) ⟶ p d : = exp ( − d 2 − 1 4 ) . (4) \mathbb{P}\left(G_{n,d}^{\mathrm{CM}}\text{ is simple}\right) \longrightarrow p_d := \exp\left(-\frac{d^2-1}{4}\right). \tag*{(4)} P ( G n , d CM is simple ) ⟶ p d := exp ( − 4 d 2 − 1 ) . (4)
Moreover, conditional on simplicity, the resulting graph is uniformly distributed over G n , d \mathcal{G}_{n,d} G n , d ; see [18 ] . Consequently, if an event A n A_n A n holds with high probability in the configuration model, then
P ( G n , d ∉ A n ) = P ( G n , d C M ∉ A n ∣ G n , d C M is simple ) = P ( G n , d C M ∉ A n ) P ( G n , d C M is simple ) ⟶ 0. \mathbb{P}\left(G_{n,d}\notin A_n\right)
=
\mathbb{P}\left(G_{n,d}^{\mathrm{CM}}\notin A_n \mid G_{n,d}^{\mathrm{CM}}\text{ is simple}\right)
=
\frac{\mathbb{P}\left(G_{n,d}^{\mathrm{CM}}\notin A_n\right)}
{\mathbb{P}\left(G_{n,d}^{\mathrm{CM}}\text{ is simple}\right)}
\longrightarrow0. P ( G n , d ∈ / A n ) = P ( G n , d CM ∈ / A n ∣ G n , d CM is simple ) = P ( G n , d CM is simple ) P ( G n , d CM ∈ / A n ) ⟶ 0.
Thus, high-probability statements transfer from the configuration model to the uniform simple model, although the converse need not hold.
Contiguity of random graph models
Contiguity allows us to transfer high-probability statements from auxiliary models with prescribed spanning structures to uniform random regular graphs. Two sequences of probability measures ( P n ) (\mathbb{P}_n) ( P n ) and ( Q n ) (\mathbb{Q}_n) ( Q n ) on the same spaces are mutually contiguous , written P n ≈ Q n \mathbb{P}_n \approx\mathbb{Q}_n P n ≈ Q n , if, for every sequence of events A n A_n A n ,
P n ( A n ) ⟶ 0 ⟺ Q n ( A n ) ⟶ 0. \mathbb{P}_n(A_n) \longrightarrow0
\quad\Longleftrightarrow\quad
\mathbb{Q}_n(A_n) \longrightarrow0. P n ( A n ) ⟶ 0 ⟺ Q n ( A n ) ⟶ 0.
Thus, the two models share the same high-probability events. Mutual contiguity is also preserved under fixed finite products, allowing its application to independent pairs of graphs.
For the planted models considered below, if Y n ( G ) Y_n(G) Y n ( G ) counts the admissible spanning structures in G G G , the unmarked planted distribution is the Y n Y_n Y n -size-biased version of the original law [10 ] , namely
d Q n d P n ( G ) = Y n ( G ) E [ Y n ] . \frac{\mathrm{d}\mathbb{Q}_n}{\mathrm{d}\mathbb{P}_n}(G)=\frac{Y_n(G)}{\mathbb{E}[Y_n]}. d P n d Q n ( G ) = E [ Y n ] Y n ( G ) .
Controlling this normalised count via small-subgraph conditioning is a standard approach to establishing contiguity for random regular graphs; see [18 ] .
This differs from conditioning the configuration model on simplicity: since simplicity has probability bounded away from zero, high-probability statements transfer to the uniform simple model, but mutual contiguity does not follow. In particular, this argument does not characterise the residual graph after selecting a spanning subgraph.
Hamilton cycles and short cycle factors
Our lower bounds rely on spanning structures that can be aligned between two independent graphs. The two constructions use these structures in different ways. For Hamilton cycles, we shall work in a planted model and transfer the resulting graph event by contiguity. For logarithmic cycle factors, we only need an existence theorem; the residual pseudorandomness required later will be proved uniformly over all factors. The first input is the classical Hamiltonicity theorem of Robinson and Wormald [15 ] .
Theorem 2.1 (Hamiltonicity of random regular graphs). For every fixed d ≥ 3 d \ge3 d ≥ 3 , a uniform simple d d d -regular graph is Hamiltonian with high probability.
We shall also use the corresponding planted-model statement. Let H H H be a uniform Hamilton cycle on [ n ] [n] [ n ] and let R R R be an independent uniform simple ( d − 2 ) (d-2) ( d − 2 ) -regular graph. Define the event
D : = { E ( H ) ∩ E ( R ) = ∅ } . D := \{E(H) \cap E(R) = \varnothing\}. D := { E ( H ) ∩ E ( R ) = ∅ } .
Conditionally on D D D , the union H ∪ R H \cup R H ∪ R is a simple d d d -regular graph. The following contiguity result is due to Wormald; see [18 Theorem 4.15(i)] .
Theorem 2.2 (Hamilton-cycle contiguity). Fix d ≥ 3 d \ge3 d ≥ 3 and let n n n be admissible. The distribution of H ∪ R ∣ D H \cup R \mid D H ∪ R ∣ D is mutually contiguous to U n , d U_{n,d} U n , d .
The second spanning structure is a k k k -cycle factor, namely a spanning collection of n / k n/k n / k vertex-disjoint cycles, each of length k k k . Kahn, Lubetzky, and Wormald [13 ] establish a sharp threshold for such factors in random cubic graphs, and state that the argument extends to every fixed degree d ≥ 3 d \ge3 d ≥ 3 . Before stating such an extension, we compute the degree-dependent first moment, which identifies the corresponding threshold location.
Proposition 2.3 (First moment for k k k -cycle factors). Fix d ≥ 3 d \ge3 d ≥ 3 , and let k = k ( n ) → ∞ k=k(n)\to\infty k = k ( n ) → ∞ satisfy k ∣ n k\mid n k ∣ n and k = O ( log n ) k=O(\log n) k = O ( log n ) . Put q = n / k q=n/k q = n / k , and let X n , k X_{n,k} X n , k denote the number of realised spanning k k k -cycle factors in the d d d -regular configuration model on [ n ] [n] [ n ] , where a realisation records the half-edge pairs used by the factor. Define
a d : = log ( d − 1 ) + d − 2 2 log ( d − 2 d ) . a_d := \log(d-1)+\frac{d-2}{2}\log\left(\frac{d-2}{d}\right). a d := log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) .
Then
log E X n , k = n a d − n k log ( 2 n / e ) + O d ( log n ) . (5) \log\mathbb{E}X_{n,k}=na_d-\frac{n}{k}\log(2n/e)+O_d(\log n). \tag*{(5)} log E X n , k = n a d − k n log ( 2 n / e ) + O d ( log n ) . (5)
In particular, if k ∼ c log n k\sim c\log n k ∼ c log n and c < a d − 1 c<a_d^{-1} c < a d − 1 , then P ( X n , k > 0 ) → 0 \mathbb{P}(X_{n,k}>0)\to0 P ( X n , k > 0 ) → 0 .
Proof. There are exactly
∣ F n , k ∣ = n ! ( 2 k ) q q ! |\mathcal{F}_{n,k}|=\frac{n!}{(2k)^{q}q!} ∣ F n , k ∣ = ( 2 k ) q q ! n !
labelled k k k -cycle factors on [ n ] [n] [ n ] . For a fixed factor F F F , choose at each vertex the two ordered half-edges that realise its two incident factor edges. This gives [ d ( d − 1 ) ] n [d(d-1)]^n [ d ( d − 1 ) ] n half-edge realizations. Once the n n n factor pairs have been selected, the remaining ( d − 2 ) n (d-2)n ( d − 2 ) n half-edges may be paired arbitrarily. Therefore
E X n , k = n ! ( 2 k ) q q ! [ d ( d − 1 ) ] n ( ( d − 2 ) n − 1 ) ! ! ( d n − 1 ) ! ! . \mathbb{E}X_{n,k}=\frac{n!}{(2k)^q q!}[d(d-1)]^n\frac{((d-2)n-1)!!}{(dn-1)!!}. E X n , k = ( 2 k ) q q ! n ! [ d ( d − 1 ) ] n ( d n − 1 )!! (( d − 2 ) n − 1 )!! .
Using ( 2 r − 1 ) ! ! = ( 2 r ) ! / ( 2 r r ! ) (2r-1)!!=(2r)!/(2^r r!) ( 2 r − 1 )!! = ( 2 r )! / ( 2 r r !) and Stirling’s formula gives
log E X n , k = n log [ d ( d − 1 ) ] + log n ! − q log ( 2 k ) − log q ! + log ( ( d − 2 ) n − 1 ) ! ! − log ( d n − 1 ) ! ! = n [ log ( d − 1 ) + d − 2 2 log ( d − 2 d ) ] − n k log ( 2 n / e ) + O d ( log n ) , \begin{aligned}
\log\mathbb{E}X_{n,k}
&=n\log[d(d-1)]+\log n!-q\log(2k)-\log q!\\
&\quad+\log((d-2)n-1)!!-\log(dn-1)!!\\
&=n\left[\log(d-1)+\frac{d-2}{2}\log\left(\frac{d-2}{d}\right)\right]-\frac{n}{k}\log(2n/e)+O_d(\log n),
\end{aligned} log E X n , k = n log [ d ( d − 1 )] + log n ! − q log ( 2 k ) − log q ! + log (( d − 2 ) n − 1 )!! − log ( d n − 1 )!! = n [ log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) ] − k n log ( 2 n / e ) + O d ( log n ) ,
which is (5).
If k ∼ c log n k\sim c\log n k ∼ c log n with c < a d − 1 c<a_d^{-1} c < a d − 1 , then for some fixed η > 0 \eta>0 η > 0 , k a d ≤ ( 1 − η ) log n ka_d\leq(1-\eta)\log n k a d ≤ ( 1 − η ) log n for all sufficiently large n n n . Hence log E X n , k → − ∞ \log\mathbb{E}X_{n,k}\to-\infty log E X n , k → − ∞ , and Markov’s inequality gives P ( X n , k > 0 ) → 0 \mathbb{P}(X_{n,k}>0)\to0 P ( X n , k > 0 ) → 0 in the configuration model. Since simplicity has probability bounded away from zero, the same non-existence conclusion holds after conditioning on simplicity. □
The preceding computation identifies the fixed-degree threshold constant. In particular, the natural location of the transition is
K d ( n ) : = log ( 2 n / e ) a d . (6) K_d(n):=\frac{\log(2n/e)}{a_d}. \tag*{(6)} K d ( n ) := a d log ( 2 n / e ) . (6)
Theorem 2.4 (Short cycle factors in fixed degree). Fix d ≥ 3 d\geq3 d ≥ 3 and let
a d = log ( d − 1 ) + d − 2 2 log ( d − 2 d ) , K d ( n ) = log ( 2 n / e ) a d . a_d=\log(d-1)+\frac{d-2}{2}\log\left(\frac{d-2}{d}\right),\qquad K_d(n)=\frac{\log(2n/e)}{a_d}. a d = log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) , K d ( n ) = a d log ( 2 n / e ) . Let k = k ( n ) k=k(n) k = k ( n ) satisfy k ∣ n , k\mid n, k ∣ n ,
k = K d ( n ) + ω ( 1 ) , k = ( 1 + o ( 1 ) ) K d ( n ) . k=K_d(n)+\omega(1),\qquad k=(1+o(1))K_d(n). k = K d ( n ) + ω ( 1 ) , k = ( 1 + o ( 1 )) K d ( n ) . Then a uniform simple d d d -regular graph contains a k k k -cycle factor with high probability. Conversely, for every fixed δ > 0 \delta>0 δ > 0 , no k k k -cycle factor exists with high probability whenever
k ≤ ( 1 a d − δ ) log n . k\leq\left(\frac{1}{a_d}-\delta\right)\log n. k ≤ ( a d 1 − δ ) log n .
For d = 3 d = 3 d = 3 , the existence follows from [13 Theorem 1] . Moreover, the authors state that their proof extends, with very few modifications, to every fixed degree d ≥ 3 d \ge3 d ≥ 3 , yielding the corresponding cycle-factor threshold and its two-point concentration. This is in line with the result we obtain in Theorem 2.3 , and we use the statement in [13 ] as a witness of the k k k -cycle factor existence with k ≥ 3 k \ge3 k ≥ 3 .
We note that the complementary non-existence result follows directly from Theorem 2.3 and Markov’s inequality, independently of the methods used in [13 ] to establish existence in cubic graphs.
Low degrees and first-order overlap
The effect of optimising over vertex permutations depends strongly on the degree. We first settle the cases d = 1 d = 1 d = 1 and d = 2 d = 2 d = 2 , where the component structure can be exploited directly. We then establish the first-order overlap for every fixed d ≥ 3 d \ge3 d ≥ 3 . In this regime, Hamiltonicity gives a baseline of n n n common edges, while a simple first-moment argument shows that the maximum overlap cannot be considerably larger at first order. The sharper upper and lower bounds on the surplus are developed in the following sections.
Degrees one and two
For d = 1 d = 1 d = 1 , every graph is a perfect matching. Since any two perfect matchings on [ n ] [n] [ n ] are isomorphic, M n = n / 2 M_n = n/2 M n = n /2 and GEDE ( G 1 , G 2 ) = 0 \operatorname{GEDE}(G_1,G_2) = 0 GEDE ( G 1 , G 2 ) = 0 deterministically. For d = 2 d = 2 d = 2 , each graph is a disjoint union of cycles of length at least three.
For a 2-regular graph G G G , let c ( G ) c(G) c ( G ) denote its number of cycles, and let γ ℓ ( G ) \gamma_\ell(G) γ ℓ ( G ) denote its number of cycles of length ℓ \ell ℓ . The following estimate describes the cycle counts needed for our argument.
Lemma 3.1 (Cycle counts in random 2-regular graphs). Let G 1 , G 2 G_1,G_2 G 1 , G 2 be independent samples from U n , 2 \mathcal{U}_{n,2} U n , 2 . Then, for i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } ,
c ( G i ) = ( 1 2 + o P ( 1 ) ) log n . c(G_i) = \left(\frac{1}{2} + o_{\mathrm{P}}(1)\right)\log n. c ( G i ) = ( 2 1 + o P ( 1 ) ) log n . Moreover,
∑ ℓ = 3 n min { γ ℓ ( G 1 ) , γ ℓ ( G 2 ) } = O P ( 1 ) . \sum_{\ell=3}^{n} \min\{\gamma_\ell(G_1),\gamma_\ell(G_2)\} = O_{\mathrm{P}}(1). ℓ = 3 ∑ n min { γ ℓ ( G 1 ) , γ ℓ ( G 2 )} = O P ( 1 ) .
Proof. We first work in the 2-regular configuration model. Write γ \gamma γ for its total number of connected components, including loops and double edges. A uniform pairing can be constructed recursively by adding one vertex at a time: with probability 1 / ( 2 j − 1 ) 1/(2j-1) 1/ ( 2 j − 1 ) , the new vertex forms a loop, and otherwise it is inserted into one of the edges of the pairing on the preceding j − 1 j-1 j − 1 vertices. Insertion preserves the number of components, whereas a loop creates one additional component. Consequently, γ \gamma γ has the distribution of a sum of independent Bernoulli random variables with respective parameters 1 / ( 2 j − 1 ) 1/(2j-1) 1/ ( 2 j − 1 ) , 1 ≤ j ≤ n 1 \le j \le n 1 ≤ j ≤ n . In particular,
E [ γ ] = ∑ j = 1 n 1 2 j − 1 = 1 2 log n + O ( 1 ) , Var ( γ ) = O ( log n ) . \mathbb{E}[\gamma] = \sum_{j=1}^{n} \frac{1}{2j-1} = \frac{1}{2}\log n + O(1), \qquad\operatorname{Var}(\gamma) = O(\log n). E [ γ ] = j = 1 ∑ n 2 j − 1 1 = 2 1 log n + O ( 1 ) , Var ( γ ) = O ( log n ) .
Chebyshev’s inequality implies γ = ( 1 / 2 + o P ( 1 ) ) log n \gamma= (1/2 + o_{\mathrm{P}}(1))\log n γ = ( 1/2 + o P ( 1 )) log n . Since the configuration model is simple with probability bounded away from zero, the same conclusion holds for the number of cycles of a uniform simple 2-regular graph.
To prove the second assertion, let γ ℓ C M \gamma_{\ell}^{\mathrm{CM}} γ ℓ CM be the number of components of length ℓ \ell ℓ in the configuration model. Counting cycles on ℓ \ell ℓ prescribed vertices and using the pairing probability gives, for 1 ≤ ℓ ≤ n 1 \le\ell\le n 1 ≤ ℓ ≤ n ,
E [ γ ℓ C M ] = 1 2 ℓ ∏ j = 0 ℓ − 1 n − j n − j − 1 2 ≤ K ℓ n n − ℓ + 1 , \mathbb{E}\left[\gamma_{\ell}^{\mathrm{CM}}\right] = \frac{1}{2\ell}\prod_{j=0}^{\ell-1}\frac{n-j}{n-j-\frac{1}{2}} \le\frac{K}{\ell}\sqrt{\frac{n}{n-\ell+1}}, E [ γ ℓ CM ] = 2 ℓ 1 j = 0 ∏ ℓ − 1 n − j − 2 1 n − j ≤ ℓ K n − ℓ + 1 n ,
where K K K is an absolute constant. Conditioning on simplicity increases the expectation of any non-negative random variable by at most the reciprocal of the simplicity probability. Hence, uniformly in ℓ \ell ℓ ,
E [ γ ℓ ( G i ) ] ≤ K ′ ℓ n n − ℓ + 1 . \mathbb{E}\left[\gamma_{\ell}(G_i)\right] \le\frac{K'}{\ell}\sqrt{\frac{n}{n-\ell+1}}. E [ γ ℓ ( G i ) ] ≤ ℓ K ′ n − ℓ + 1 n .
for another absolute constant K ′ K' K ′ . By independence and min ( x , y ) ≤ x y \min(x,y) \le xy min ( x , y ) ≤ x y for non-negative integers x , y x,y x , y ,
E [ ∑ ℓ = 3 n min { γ ℓ ( G 1 ) , γ ℓ ( G 2 ) } ] ≤ ∑ ℓ = 3 n E [ γ ℓ ( G 1 ) ] E [ γ ℓ ( G 2 ) ] ≤ ( K ′ ) 2 ∑ ℓ = 3 n n ℓ 2 ( n − ℓ + 1 ) = O ( 1 ) . \mathbb{E}\left[\sum_{\ell=3}^{n}\min\{\gamma_{\ell}(G_1),\gamma_{\ell}(G_2)\}\right] \le\sum_{\ell=3}^{n}\mathbb{E}\left[\gamma_{\ell}(G_1)\right]\mathbb{E}\left[\gamma_{\ell}(G_2)\right] \le(K')^2\sum_{\ell=3}^{n}\frac{n}{\ell^2(n-\ell+1)} = O(1). E [ ℓ = 3 ∑ n min { γ ℓ ( G 1 ) , γ ℓ ( G 2 )} ] ≤ ℓ = 3 ∑ n E [ γ ℓ ( G 1 ) ] E [ γ ℓ ( G 2 ) ] ≤ ( K ′ ) 2 ℓ = 3 ∑ n ℓ 2 ( n − ℓ + 1 ) n = O ( 1 ) .
The last sum is bounded by splitting at ℓ = n / 2 \ell=n/2 ℓ = n /2 : the first part is O ( ∑ ℓ ≥ 1 ℓ − 2 ) O(\sum_{\ell\ge1}\ell^{-2}) O ( ∑ ℓ ≥ 1 ℓ − 2 ) , and the second is O ( log n / n ) O(\log n/n) O ( log n / n ) . Markov’s inequality completes the proof. □
We now prove Theorem 1.2 . For the lower bound, we remove one edge from each cycle and concatenate the resulting paths to construct an alignment. For the upper bound, we associate a bipartite multigraph with the common graph, whose vertices represent the cycles of both graphs. We control the number of connected components through an elementary first-moment argument, which yields the leading-order asymptotics.
Proof of Theorem 1.2 . For the lower bound, remove one edge from each cycle of G i G_i G i , obtaining c i c_i c i vertex-disjoint paths. Concatenate these paths to form an ordering of the vertices of G i G_i G i , and align the two orderings. Among the n − 1 n-1 n − 1 consecutive pairs in either ordering, exactly c i − 1 c_i-1 c i − 1 are not edges of G i G_i G i . Hence
M n ≥ n − c 1 − c 2 + 1. (7) M_n \ge n-c_1-c_2+1. \tag*{(7)} M n ≥ n − c 1 − c 2 + 1. (7)
Next, we consider the upper bound. Fix a permutation π \pi π and identify the vertices through it. Let
J = π ( G 1 ) ∩ G 2 J=\pi(G_1)\cap G_2 J = π ( G 1 ) ∩ G 2
be the common graph. Construct a bipartite multigraph B B B whose vertices represent the cycles of π ( G 1 ) \pi(G_1) π ( G 1 ) and G 2 G_2 G 2 , with one edge for each connected component of J J J , including isolated vertices. Let b b b be the number of connected components of B B B , and let r r r be the number of cyclic components of J J J . Since J J J has maximum degree two, its number of connected components is
n − Ov π ( G 1 , G 2 ) + r . n-\operatorname{Ov}_{\pi}(G_1,G_2)+r. n − Ov π ( G 1 , G 2 ) + r .
This is also the number of edges of B B B . As B B B has c 1 + c 2 c_1+c_2 c 1 + c 2 vertices and b b b connected components, it follows that n − Ov π ( G 1 , G 2 ) + r ≥ c 1 + c 2 − b n-\operatorname{Ov}_{\pi}(G_1,G_2)+r \ge c_1+c_2-b n − Ov π ( G 1 , G 2 ) + r ≥ c 1 + c 2 − b . Consequently,
Ov π ( G 1 , G 2 ) ≤ n − c 1 − c 2 + b + r . (8) \operatorname{Ov}_{\pi}(G_1,G_2) \le n-c_1-c_2+b+r. \tag*{(8)} Ov π ( G 1 , G 2 ) ≤ n − c 1 − c 2 + b + r . (8)
Since every cyclic component of J J J must be an entire cycle of the same length in both graphs, from Theorem 3.1 it follows r = O P ( 1 ) r=O_{\mathrm P}(1) r = O P ( 1 ) , uniformly in π \pi π . It remains to control b b b . For i = 1 , 2 i=1,2 i = 1 , 2 and 0 ≤ k ≤ n 0\le k\le n 0 ≤ k ≤ n , let A i , k A_{i,k} A i , k be the number of k k k -vertex subsets of G i G_i G i that are unions of cycles. Define
T = ∑ k = 0 n A 1 , k A 2 , k . T=\sum_{k=0}^{n} A_{1,k}A_{2,k}. T = k = 0 ∑ n A 1 , k A 2 , k .
Thus T T T counts pairs of unions of cycles, one from each graph, having the same number of vertices.
Every connected component of B B B corresponds to a nonempty set of vertices that is a union of cycles in both graphs. Taking arbitrary unions of these b b b disjoint sets gives 2 b 2^b 2 b distinct pairs counted by T T T . In particular,
2 b ≤ T . (9) 2^b\le T. \tag*{(9)} 2 b ≤ T . (9)
We show that E [ T ] = O ( log n ) \mathbb{E}[T]=O(\log n) E [ T ] = O ( log n ) . First, consider the 2-regular configuration model. Applying a standard argument for the configuration model, one obtains
E C M [ A i , k ] = ( n k ) ( 2 k − 1 ) ! ! ( 2 ( n − k ) − 1 ) ! ! ( 2 n − 1 ) ! ! . \mathbb{E}_{\mathrm{CM}}[A_{i,k}]=\binom{n}{k}\frac{(2k-1)!!(2(n-k)-1)!!}{(2n-1)!!}. E CM [ A i , k ] = ( k n ) ( 2 n − 1 )!! ( 2 k − 1 )!! ( 2 ( n − k ) − 1 )!! .
Using the standard estimate ( 2 m m ) ≲ 4 m / m + 1 \binom{2m}{m}\lesssim4^m/\sqrt{m+1} ( m 2 m ) ≲ 4 m / m + 1 , we obtain, uniformly in 0 ≤ k ≤ n 0\le k\le n 0 ≤ k ≤ n ,
E C M [ A i , k ] = ( 2 k k ) ( 2 ( n − k ) n − k ) ( 2 n n ) = O ( n + 1 ( k + 1 ) ( n − k + 1 ) ) . \mathbb{E}_{\mathrm{CM}}[A_{i,k}]=\frac{\binom{2k}{k}\binom{2(n-k)}{n-k}}{\binom{2n}{n}}=O\left(\sqrt{\frac{n+1}{(k+1)(n-k+1)}}\right). E CM [ A i , k ] = ( n 2 n ) ( k 2 k ) ( n − k 2 ( n − k ) ) = O ( ( k + 1 ) ( n − k + 1 ) n + 1 ) .
Since the probability of simplicity is bounded away from zero, conditioning on simplicity increases these expectations by at most a constant factor C C C . Hence, using independence of G 1 , G 2 G_1,G_2 G 1 , G 2 we conclude that
E [ T ] = ∑ k = 0 n E [ A 1 , k ] E [ A 2 , k ] ≤ C 2 ∑ k = 0 n E C M [ A 1 , k ] E C M [ A 2 , k ] = O ( log n ) . \mathbb{E}[T]=\sum_{k=0}^{n}\mathbb{E}[A_{1,k}]\mathbb{E}[A_{2,k}]
\le C^2\sum_{k=0}^{n}\mathbb{E}_{\mathrm{CM}}[A_{1,k}]\mathbb{E}_{\mathrm{CM}}[A_{2,k}]
=O(\log n). E [ T ] = k = 0 ∑ n E [ A 1 , k ] E [ A 2 , k ] ≤ C 2 k = 0 ∑ n E CM [ A 1 , k ] E CM [ A 2 , k ] = O ( log n ) .
By Markov’s inequality, T = O P ( log n ) T=O_{\mathbb{P}}(\log n) T = O P ( log n ) , which, together with (9) , yields
b ≤ log 2 log n + O P ( 1 ) . b\le\log_2\log n+O_{\mathbb{P}}(1). b ≤ log 2 log n + O P ( 1 ) .
This bound holds simultaneously for all permutations π \pi π , since T T T depends only on the two original graphs. Combining this with (8) and r = O P ( 1 ) r=O_{\mathbb{P}}(1) r = O P ( 1 ) , we obtain
M n ≤ n − c 1 − c 2 + O P ( log log n ) . M_n\le n-c_1-c_2+O_{\mathbb{P}}(\log\log n). M n ≤ n − c 1 − c 2 + O P ( log log n ) .
This proves the claim.
It is possible to obtain a stronger upper bound than the one derived in the proof above. In particular, M n ≤ n − c 1 − c 2 + O P ( 1 ) M_n\le n-c_1-c_2+O_{\mathbb{P}}(1) M n ≤ n − c 1 − c 2 + O P ( 1 ) . In fact, let L i \mathcal{L}_i L i be the set of subset sums of the cycle lengths of G i G_i G i , and put
Z = ∣ ( L 1 ∩ L 2 ) ∖ { 0 , n } ∣ . Z=\lvert(\mathcal{L}_1\cap\mathcal{L}_2)\setminus\{0,n\}\rvert. Z = ∣( L 1 ∩ L 2 ) ∖ { 0 , n }∣ .
Each connected component of B B B corresponds to a nonempty vertex set that is a union of entire cycles in both graphs. Ordering these b b b sets and taking successive partial unions produces b − 1 b-1 b − 1 distinct nontrivial common subset sums. Hence
b ≤ Z + 1. (10) b\le Z+1. \tag*{(10)} b ≤ Z + 1. (10)
The probabilistic estimate Z = O P ( 1 ) Z=O_{\mathbb{P}}(1) Z = O P ( 1 ) is established in Section A of the appendix.
Hamiltonian baseline and first-order overlap
We now consider fixed d ≥ 3 d \ge3 d ≥ 3 . By Theorem 2.1 , both G 1 G_1 G 1 and G 2 G_2 G 2 contain Hamilton cycles with high probability. Mapping one Hamilton cycle onto the other preserves all n n n cycle edges and therefore gives M n ≥ n M_n \ge n M n ≥ n with high probability. This is the baseline that we shall improve in § 5 and § 6 .
To establish the first-order result, it remains to show that M n M_n M n cannot exceed ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n with high probability. A simple union bound suffices; § 4 will refine this argument to capture the surplus of order n / log n n/\log n n / log n .
Proof of Theorem 1.3. The lower bound follows from the Hamiltonian alignment described above. For the upper bound, fix ε > 0 \varepsilon> 0 ε > 0 sufficiently small that 2 ( 1 + ε ) < d 2(1+\varepsilon)<d 2 ( 1 + ε ) < d , and set t = ⌈ ( 1 + ε ) n ⌉ t=\lceil(1+\varepsilon)n\rceil t = ⌈( 1 + ε ) n ⌉ . Condition on G 1 G_1 G 1 . If M n ≥ t M_n \ge t M n ≥ t , there exist a permutation π ∈ S n \pi\in S_n π ∈ S n and a set F ⊆ E ( G 1 ) F \subseteq E(G_1) F ⊆ E ( G 1 ) of t t t edges such that π ( F ) ⊆ E ( G 2 ) \pi(F) \subseteq E(G_2) π ( F ) ⊆ E ( G 2 ) .
For a prescribed set of t t t edges, the configuration model gives at most d 2 t d^{2t} d 2 t choices of half-edges to realise their incidences. By (3) , the probability of any prescribed pairing is at most
∏ j = 0 t − 1 1 d n − 2 j − 1 ≤ ( 1 d n − 2 t + 1 ) t \prod_{j=0}^{t-1}\frac{1}{dn-2j-1}\leq\left(\frac{1}{dn-2t+1}\right)^t j = 0 ∏ t − 1 d n − 2 j − 1 1 ≤ ( d n − 2 t + 1 1 ) t
Since d n − 2 t dn-2t d n − 2 t is bounded below by a positive constant times n n n , and conditioning on simplicity costs only a bounded factor, there is a constant K = K ( d , ε ) K=K(d,\varepsilon) K = K ( d , ε ) such that
P ( π ( F ) ⊆ E ( G 2 ) ) ≤ ( K n ) t . \mathbb{P}\bigl(\pi(F)\subseteq E(G_2)\bigr)\leq\left(\frac{K}{n}\right)^t. P ( π ( F ) ⊆ E ( G 2 ) ) ≤ ( n K ) t .
A union bound over the n ! n! n ! permutations and the ( n d / 2 t ) \binom{nd/2}{t} ( t n d /2 ) choices of F F F now yields
P ( M n ≥ t ) ≤ n ! ( n d / 2 t ) ( K n ) t . \mathbb{P}(M_n\geq t)\leq n!\binom{nd/2}{t}\left(\frac{K}{n}\right)^t. P ( M n ≥ t ) ≤ n ! ( t n d /2 ) ( n K ) t .
Using ( n d / 2 t ) ≤ 2 n d / 2 \binom{nd/2}{t}\leq2^{nd/2} ( t n d /2 ) ≤ 2 n d /2 and Stirling’s formula, we obtain
log P ( M n ≥ t ) ≤ n log n − t log n + O d , ε ( n ) = − ε n log n + O d , ε ( n ) ⟶ − ∞ . \log\mathbb{P}(M_n\geq t)\leq n\log n-t\log n+O_{d,\varepsilon}(n)=-\varepsilon n\log n+O_{d,\varepsilon}(n)\longrightarrow-\infty. log P ( M n ≥ t ) ≤ n log n − t log n + O d , ε ( n ) = − ε n log n + O d , ε ( n ) ⟶ − ∞.
Thus P ( M n ≥ ( 1 + ε ) n ) → 0 \mathbb{P}(M_n\geq(1+\varepsilon)n)\to0 P ( M n ≥ ( 1 + ε ) n ) → 0 . Since it suffices to prove this for arbitrarily small ε > 0 \varepsilon>0 ε > 0 , the Hamiltonian lower bound implies M n / n → P 1 M_n/n\xrightarrow{\mathbb{P}}1 M n / n P 1 . □
The upper bound
We now refine the first-moment argument of § 3 to the scale of the surplus above the Hamiltonian baseline. The first-order argument counts arbitrary common edge sets. At second order, this is too wasteful: if an aligned intersection contains n + s n+s n + s edges, then the relevant quantity is not its total size but its graph excess. We therefore first remove the tree-like part of the intersection and reduce the problem to counting common subgraphs of minimum degree at least two. For a finite graph H H H , write
δ ( H ) : = min u ∈ V ( H ) deg ( u ) , Δ ( H ) : = max u ∈ V ( H ) deg ( u ) , ex ( H ) : = ∣ E ( H ) ∣ − ∣ V ( H ) ∣ . \delta(H):=\min_{u\in V(H)}\deg(u),\qquad\Delta(H):=\max_{u\in V(H)}\deg(u),\qquad\operatorname{ex}(H):=|E(H)|-|V(H)|. δ ( H ) := u ∈ V ( H ) min deg ( u ) , Δ ( H ) := u ∈ V ( H ) max deg ( u ) , ex ( H ) := ∣ E ( H ) ∣ − ∣ V ( H ) ∣.
The proof of Theorem 1.4 has three steps. Suppose that M n ≥ n + s M_n\geq n+s M n ≥ n + s .
Extract a structural witness. From an aligned intersection with at least n + s n+s n + s edges, we extract a common graph H H H (a core) with minimum degree at least two and ex ( H ) = s \operatorname{ex}(H)=s ex ( H ) = s . Thus, the surplus becomes exactly the excess of a common core.
Count common cores. If H H H has v v v vertices, let Z v , s Z_{v,s} Z v , s count such common core witnesses. A configuration-model enumeration gives, uniformly for s = O ( n / log n ) s=O(n/\log n) s = O ( n / log n ) ,
log E Z v , s ≤ n f d ( v / n ) − s log n + O d ( s log n s + log n ) , \log\mathbb{E}Z_{v,s} \le n f_d(v/n)-s\log n+O_d\left(s\log\frac{n}{s}+\log n\right), log E Z v , s ≤ n f d ( v / n ) − s log n + O d ( s log s n + log n ) ,
where the leading term n f d ( v / n ) n f_d(v/n) n f d ( v / n ) quantifies the entropy of a core occupying a fraction v / n v/n v / n of the vertices.
Optimise over the core size. The entropy function f d f_d f d is maximised at v / n = d / ( d + 1 ) v/n=d/(d+1) v / n = d / ( d + 1 ) , attaining value b d b_d b d . Markov’s inequality and a union bound over v v v conclude the proof.
From surplus overlap to a common core
We begin by extracting a common core between G 1 G_1 G 1 and G 2 G_2 G 2 with prescribed excess.
Lemma 4.1 (Exact-excess core reduction). Let J J J be a simple graph on at most n n n vertices with at least n + s n+s n + s edges, where s ≥ 1 s\ge1 s ≥ 1 , and suppose Δ ( J ) ≤ d \Delta(J)\le d Δ ( J ) ≤ d . Then J J J contains a nonempty subgraph H H H such that
δ ( H ) ≥ 2 , Δ ( H ) ≤ d , ex ( H ) = s . \delta(H)\ge2,\qquad\Delta(H)\le d,\qquad\operatorname{ex}(H)=s. δ ( H ) ≥ 2 , Δ ( H ) ≤ d , ex ( H ) = s .
Proof. Add isolated vertices, if necessary, so that J J J is viewed as a graph on exactly n n n vertices. Repeatedly delete vertices of degree zero or one, together with all incident edges. Deleting an isolated vertex increases ∣ E ∣ − ∣ V ∣ |E|-|V| ∣ E ∣ − ∣ V ∣ by one, while deleting a degree-one vertex leaves ∣ E ∣ − ∣ V ∣ |E|-|V| ∣ E ∣ − ∣ V ∣ unchanged. Hence the resulting 2-core K K K satisfies
δ ( K ) ≥ 2 , ex ( K ) ≥ ex ( J ) ≥ s . \delta(K)\ge2,\qquad\operatorname{ex}(K)\ge\operatorname{ex}(J)\ge s. δ ( K ) ≥ 2 , ex ( K ) ≥ ex ( J ) ≥ s .
Since s > 0 s>0 s > 0 , the core is nonempty.
If ex ( K ) = s \operatorname{ex}(K)=s ex ( K ) = s , take H = K H=K H = K . Otherwise, choose a connected component C C C of K K K with positive excess. Such a component contains a non-bridge edge e e e . Delete e e e and then repeatedly prune every degree-one vertex that is created. Deleting e e e lowers the excess by exactly one, while each subsequent pruning step removes one vertex and one edge and therefore leaves the excess unchanged. Moreover, C − e C-e C − e still contains a cycle, so the pruning procedure leaves a nonempty graph of minimum degree at least two. Thus, one application of this operation lowers the total excess by exactly one and never increases the maximum degree. Iterating until the total excess is s s s returns H H H .
Corollary 4.2. If M n ≥ n + s M_n\ge n+s M n ≥ n + s , then for some 1 ≤ v ≤ n 1\le v\le n 1 ≤ v ≤ n there exist vertex sets V 1 , V 2 ⊆ [ n ] V_1,V_2\subseteq[n] V 1 , V 2 ⊆ [ n ] of size v v v , a bijection ϕ : V 1 → V 2 \phi:V_1\to V_2 ϕ : V 1 → V 2 , and a simple graph H H H on V 1 V_1 V 1 such that
∣ E ( H ) ∣ = v + s , 2 ≤ deg H ( u ) ≤ d ( u ∈ V 1 ) , |E(H)|=v+s,\qquad2\le\deg_H(u)\le d\quad(u\in V_1), ∣ E ( H ) ∣ = v + s , 2 ≤ deg H ( u ) ≤ d ( u ∈ V 1 ) , and
H ⊆ G 1 [ V 1 ] , ϕ ( H ) ⊆ G 2 [ V 2 ] . H\subseteq G_1[V_1],\qquad\phi(H)\subseteq G_2[V_2]. H ⊆ G 1 [ V 1 ] , ϕ ( H ) ⊆ G 2 [ V 2 ] .
Proof. Choose a permutation attaining at least n + s n+s n + s common edges and identify the corresponding aligned intersection with a graph J J J on [ n ] [n] [ n ] . Since both ambient graphs are d d d -regular, Δ ( J ) ≤ d \Delta(J)\le d Δ ( J ) ≤ d . Apply Theorem 4.1 and then undo the identification of the two vertex sets. ∫
The point of Theorem 4.2 is that the surplus is now encoded by a much more rigid witness. Tree-like extensions of the aligned intersection disappear under the 2 2 2 -core reduction, while the quantity ∣ E ∣ − ∣ V ∣ |E|-|V| ∣ E ∣ − ∣ V ∣ , which records the surplus, is preserved.
A first-moment bound for common cores
We first work with two independent d d d -regular configuration models. Conditioning both models on simplicity changes the upper bounds on the probability only by a constant factor p d p_d p d defined in (4).
Fix integers v ≤ n v \le n v ≤ n and s ≥ 1 s \ge1 s ≥ 1 , and put m = v + s m=v+s m = v + s . Let Z v , s Z_{v,s} Z v , s count choices of vertex sets V 1 , V 2 ⊆ [ n ] V_1,V_2 \subseteq[n] V 1 , V 2 ⊆ [ n ] of size v v v , a bijection ϕ : V 1 → V 2 \phi:V_1 \to V_2 ϕ : V 1 → V 2 , and a simple graph H H H on V 1 V_1 V 1 having m m m edges and all degrees in { 2 , … , d } \{2,\ldots,d\} { 2 , … , d } , such that
H ⊆ G 1 [ V 1 ] , ϕ ( H ) ⊆ G 2 [ V 2 ] . H \subseteq G_1[V_1], \qquad\phi(H) \subseteq G_2[V_2]. H ⊆ G 1 [ V 1 ] , ϕ ( H ) ⊆ G 2 [ V 2 ] .
Define, for 0 ≤ x ≤ 1 0 \le x \le1 0 ≤ x ≤ 1 ,
f d ( x ) : = − 2 ( 1 − x ) log ( 1 − x ) + 2 x log [ d ( d − 1 ) ] − d log d + ( d − 2 x ) log ( d − 2 x ) , (11) f_d(x):=-2(1-x)\log(1-x)+2x\log[d(d-1)]-d\log d+(d-2x)\log(d-2x), \tag*{(11)} f d ( x ) := − 2 ( 1 − x ) log ( 1 − x ) + 2 x log [ d ( d − 1 )] − d log d + ( d − 2 x ) log ( d − 2 x ) , (11)
with the convention 0 log 0 = 0 0\log0=0 0 log 0 = 0 . The following proposition contains all the technical enumeration needed for the upper bound.
Proposition 4.3 (First moment for common cores). Fix d ≥ 3 d \ge3 d ≥ 3 . Uniformly over feasible integers v v v and over integers s s s satisfying 1 ≤ s = O ( n / log n ) 1 \le s=O(n/\log n) 1 ≤ s = O ( n / log n ) ,
log E Z v , s ≤ n f d ( v / n ) − s log n + O d ( s log n s + log n ) . (12) \log\mathbb{E}Z_{v,s} \le nf_d(v/n)-s\log n+O_d\left(s\log\frac{n}{s}+\log n\right). \tag*{(12)} log E Z v , s ≤ n f d ( v / n ) − s log n + O d ( s log s n + log n ) . (12)
The proof is not particularly complex, but rather technical, and it is given in Section B. We briefly indicate where the three terms in (12) come from. The quantity n f d ( v / n ) nf_d(v/n) n f d ( v / n ) is the exponential entropy of an excess-zero core occupying a fraction v / n v/n v / n of the vertices. Raising the excess from 0 0 0 to s s s changes the pairing probability by a factor n − s e O d ( s ) n^{-s}e^{O_d(s)} n − s e O d ( s ) , producing the term − s log n -s\log n − s log n . Finally, the 2 s 2s 2 s units of degree above the minimum value two can be distributed among the v v v vertices in at most
exp { O d ( s log n s ) } \exp\left\{O_d\left(s\log\frac{n}{s}\right)\right\} exp { O d ( s log s n ) }
ways. Thus, the main exponential competition is between the entropy of the core size and the n − s n^{-s} n − s cost of the surplus.
Optimising the core size
The optimisation left by Theorem 4.3 is elementary but important: it identifies which core sizes are most “dangerous” for the first-moment argument.
Lemma 4.4 (Optimising the core entropy). The function f d f_d f d is strictly concave on [ 0 , 1 ] [0,1] [ 0 , 1 ] and has unique maximiser
x d ∗ = d d + 1 , f d ( x d ∗ ) = d log ( d − 1 ) − ( d − 2 ) log ( d + 1 ) = : b d . (13) x_d^*=\frac{d}{d+1}, \qquad f_d(x_d^*)=d\log(d-1)-(d-2)\log(d+1)=:b_d. \tag*{(13)} x d ∗ = d + 1 d , f d ( x d ∗ ) = d log ( d − 1 ) − ( d − 2 ) log ( d + 1 ) =: b d . (13)
Proof. Differentiating (11),
f d ′ ( x ) = 2 log ( d ( d − 1 ) ( 1 − x ) d − 2 x ) f'_d(x)=2\log\left(\frac{d(d-1)(1-x)}{d-2x}\right) f d ′ ( x ) = 2 log ( d − 2 x d ( d − 1 ) ( 1 − x ) )
and
f d ′ ′ ( x ) = − 2 ( d − 2 ) ( 1 − x ) ( d − 2 x ) < 0 , 0 < x < 1. f''_d(x)=-\frac{2(d-2)}{(1-x)(d-2x)}<0,\qquad0<x<1. f d ′′ ( x ) = − ( 1 − x ) ( d − 2 x ) 2 ( d − 2 ) < 0 , 0 < x < 1.
Thus f d f_d f d is strictly concave. Solving f d ′ ( x ) = 0 f'_d(x)=0 f d ′ ( x ) = 0 gives x = d / ( d + 1 ) x=d/(d+1) x = d / ( d + 1 ) , and substituting this value into (11) yields (13).
Theorem 4.5 (Second-order upper tail). Fix d ≥ 3 d\ge3 d ≥ 3 and let 1 ≤ s = O ( n / log n ) 1\le s=O(n/\log n) 1 ≤ s = O ( n / log n ) be an integer. Then
log P ( M n ≥ n + s ) ≤ b d n − s log n + O d ( s log n s + log n ) . (14) \log\mathbb{P}(M_n\ge n+s)\le b_dn-s\log n+O_d\left(s\log\frac{n}{s}+\log n\right). \tag*{(14)} log P ( M n ≥ n + s ) ≤ b d n − s log n + O d ( s log s n + log n ) . (14)
Proof. By Theorem 4.2, on the event { M n ≥ n + s } \{M_n\ge n+s\} { M n ≥ n + s } there is at least one common core counted by Z v , s Z_{v,s} Z v , s for some v v v . Theorem 4.3 and Theorem 4.4 imply, uniformly over feasible v v v ,
log E Z v , s ≤ b d n − s log n + O d ( s log n s + log n ) . \log\mathbb{E}Z_{v,s}\le b_dn-s\log n+O_d\left(s\log\frac{n}{s}+\log n\right). log E Z v , s ≤ b d n − s log n + O d ( s log s n + log n ) .
There are at most n n n choices for v v v . Hence Markov’s inequality and a union bound give (14), up to an additional O ( log n ) O(\log n) O ( log n ) term. Conditioning both configurations on simplicity multiplies the probability by at most ( p d + o ( 1 ) ) − 2 (p_d+o(1))^{-2} ( p d + o ( 1 ) ) − 2 , which is absorbed in the error term.
Proof of Theorem 1.4. Apply Theorem 4.5. Next, take
s = ⌈ ( b d + ε ) n log n ⌉ . s=\left\lceil(b_d+\varepsilon)\frac{n}{\log n}\right\rceil. s = ⌈ ( b d + ε ) log n n ⌉ .
Since
s log n s = O ( n log log n log n ) = o ( n ) , s\log\frac{n}{s}=O\left(\frac{n\log\log n}{\log n}\right)=o(n), s log s n = O ( log n n log log n ) = o ( n ) ,
we obtain
log P ( M n ≥ n + s ) ≤ − ε n + o ( n ) ⟶ − ∞ . \log\mathbb{P}(M_n\ge n+s)\le-\varepsilon n+o(n)\longrightarrow-\infty. log P ( M n ≥ n + s ) ≤ − ε n + o ( n ) ⟶ − ∞.
Recall that the lower-bound constant appearing in Theorem 1.5 is
a d : = log ( d − 1 ) + d − 2 2 log ( d − 2 d ) . a_d:=\log(d-1)+\frac{d-2}{2}\log\left(\frac{d-2}{d}\right). a d := log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) .
Evaluating the entropy function at the spanning value x = 1 x=1 x = 1 gives
f d ( 1 ) = 2 a d . f_d(1)=2a_d. f d ( 1 ) = 2 a d .
If one knew that every overlap with surplus s s s contained a spanning witness with minimum degree two, the same first-moment calculation would lead to the smaller upper coefficient 2 a d 2a_d 2 a d . The core reduction gives no such information: pruning degree-zero and degree-one vertices may remove a linear fraction of the vertices. Once all core sizes are allowed, the entropy function is maximised instead at
x d ∗ = d d + 1 < 1 , x_d^*=\frac{d}{d+1}<1, x d ∗ = d + 1 d < 1 ,
and the resulting coefficient is
b d = f d ( x d ∗ ) > f d ( 1 ) = 2 a d . (15) b_d=f_d(x_d^*)>f_d(1)=2a_d. \tag*{(15)} b d = f d ( x d ∗ ) > f d ( 1 ) = 2 a d . (15)
Indeed,
b d − 2 a d = ( d − 2 ) log ( d ( d − 1 ) ( d + 1 ) ( d − 2 ) ) > 0. b_d-2a_d=(d-2)\log\left(\frac{d(d-1)}{(d+1)(d-2)}\right)>0. b d − 2 a d = ( d − 2 ) log ( ( d + 1 ) ( d − 2 ) d ( d − 1 ) ) > 0.
The interpretation is only a statement about the present first-moment bound: among the witnesses over which we union-bound, non-spanning cores of size about d n / ( d + 1 ) dn/(d+1) d n / ( d + 1 ) carry the largest entropy. It does not prove that the 2-core of an optimal alignment typically has this size. Improving b d b_d b d toward 2 a d 2a_d 2 a d , or below it, would therefore require additional structural information that rules out or more sharply penalises these non-spanning witnesses.
Alignment of Hamiltonian cycles
In Section 3, Hamiltonicity gave the baseline M n ≥ n M_n\ge n M n ≥ n with high probability. We now ask how much one can improve this overlap while keeping the Hamiltonian alignment essentially fixed. More precisely, once Hamilton cycles
H 1 = ( v 0 , … , v n − 1 ) ⊆ G 1 , H 2 = ( w 0 , … , w n − 1 ) ⊆ G 2 H_1=(v_0,\ldots,v_{n-1})\subseteq G_1,\qquad H_2=(w_0,\ldots,w_{n-1})\subseteq G_2 H 1 = ( v 0 , … , v n − 1 ) ⊆ G 1 , H 2 = ( w 0 , … , w n − 1 ) ⊆ G 2
have been chosen, we only allow cyclic shifts of the identification between them. For s ∈ Z n s\in\mathbb{Z}_n s ∈ Z n , write
ρ s ( x ) = x + s ( m o d n ) , \rho_s(x)=x+s\pmod n, ρ s ( x ) = x + s ( mod n ) ,
and use the same notation for the induced action on edges and edge sets. In cyclic coordinates, the corresponding alignment is
π s ( v i ) = w i + s , i ∈ Z n . \pi_s(v_i)=w_{i+s},\qquad i\in\mathbb{Z}_n. π s ( v i ) = w i + s , i ∈ Z n .
Every such shift preserves all n n n Hamilton-cycle edges. The first result shows that these n n n restricted alignments already yield a substantial surplus.
Theorem 5.1 (Hamilton-cycle surplus). Fix d ≥ 3 d\ge3 d ≥ 3 and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . Let G 1 , G 2 G_1,G_2 G 1 , G 2 be independent uniform simple d d d -regular graphs on [ n ] [n] [ n ] , with n n n even. With high probability, there exist Hamilton cycles
H 1 = ( v 0 , … , v n − 1 ) ⊆ G 1 , H 2 = ( w 0 , … , w n − 1 ) ⊆ G 2 , H_1=(v_0,\ldots,v_{n-1})\subseteq G_1,\qquad H_2=(w_0,\ldots,w_{n-1})\subseteq G_2, H 1 = ( v 0 , … , v n − 1 ) ⊆ G 1 , H 2 = ( w 0 , … , w n − 1 ) ⊆ G 2 , and a shift s ∈ Z n s\in\mathbb{Z}_n s ∈ Z n such that
∣ π s ( E ( G 1 ) ) ∩ E ( G 2 ) ∣ ≥ n + ⌊ ( 1 − ε ) log n log log n ⌋ . \left|\pi_s(E(G_1))\cap E(G_2)\right|\ge n+\left\lfloor(1-\varepsilon)\frac{\log n}{\log\log n}\right\rfloor. ∣ π s ( E ( G 1 )) ∩ E ( G 2 ) ∣ ≥ n + ⌊ ( 1 − ε ) log log n log n ⌋ .
In fact, the planted-model argument gives more than existence: a typical pair of Hamilton cycles works.
Theorem 5.2 (Typical Hamilton-cycle pairs). Fix d ≥ 3 d\ge3 d ≥ 3 and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and let G 1 , G 2 G_1,G_2 G 1 , G 2 be independent uniform simple d d d -regular graphs on [ n ] [n] [ n ] , with n n n even. With high probability, all but an o ( 1 ) o(1) o ( 1 ) proportion of pairs of Hamilton cycles
H 1 ⊆ G 1 , H 2 ⊆ G 2 , H_1\subseteq G_1,\qquad H_2\subseteq G_2, H 1 ⊆ G 1 , H 2 ⊆ G 2 ,
admit a cyclic alignment whose overlap is at least
n + ⌊ ( 1 − ε ) log n log log n ⌋ . n+\left\lfloor(1-\varepsilon)\frac{\log n}{\log\log n}\right\rfloor. n + ⌊ ( 1 − ε ) log log n log n ⌋ .
Equivalently, after sampling G 1 G_1 G 1 and G 2 G_2 G 2 , if one Hamilton cycle is then chosen uniformly from each graph, independently conditional on the graphs, the conditional probability that the selected pair admits such an alignment tends to one in probability.
The precise formulation in terms of the random proportion of good Hamilton-cycle pairs, together with the proof, is given in Section C. The argument to prove Theorem 5.1 makes use of three conceptual steps.
Reduction to a planted model. We first work with a contiguous random graph defined through
where H H H is a uniform Hamilton cycle and R R R is a uniform simple ( d − 2 ) (d-2) ( d − 2 ) -regular graph.
Rotations of the Hamilton cycle. Once the two planted Hamilton cycles are identified with the standard cycle on Z n \mathbb{Z}_n Z n , every cyclic shift preserves their n n n edges. The problem, therefore, reduces to finding a shift s s s for which
∣ ρ s ( E ( R 1 ) ) ∩ E ( R 2 ) ∣ \left|\rho_s(E(R_1))\cap E(R_2)\right| ∣ ρ s ( E ( R 1 )) ∩ E ( R 2 ) ∣
is large. From each residual graph, we extract a uniformly distributed matching, and the main probabilistic input is provided by showing that among their n n n cyclic shifts, one has overlap of order log n / log log n \log n/\log\log n log n / log log n .
Returning to U n , d U_{n,d} U n , d . The residual-overlap event survives the edge-disjointness conditioning because that conditioning has probability bounded away from zero. We then forget the distinguished Hamilton cycles and transfer the resulting unmarked graph event to the uniform model by contiguity.
The random-matching input
Lemma 5.3 (A successful cyclic shift). Fix c ∈ ( 0 , 1 / 2 ] c\in(0,1/2] c ∈ ( 0 , 1/2 ] and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . For i = 1 , 2 i=1,2 i = 1 , 2 , let J i J_i J i be independent uniform matchings of sizes a i a_i a i on Z n \mathbb{Z}_n Z n , where
c n ≤ a i ≤ n / 2. cn\leq a_i\leq n/2. c n ≤ a i ≤ n /2. Set
k = ⌊ ( 1 − ε ) log n log log n ⌋ . k=\left\lfloor(1-\varepsilon)\frac{\log n}{\log\log n}\right\rfloor. k = ⌊ ( 1 − ε ) log log n log n ⌋ . Then
P ( max s ∈ Z n ∣ ρ s ( J 1 ) ∩ J 2 ∣ ≥ k ) ⟶ 1 , \mathbb{P}\left(\max_{s\in\mathbb{Z}_n}\left|\rho_s(J_1)\cap J_2\right|\geq k\right)\longrightarrow1, P ( s ∈ Z n max ∣ ρ s ( J 1 ) ∩ J 2 ∣ ≥ k ) ⟶ 1 , uniformly over the allowed values of a 1 , a 2 a_1,a_2 a 1 , a 2 .
Let us briefly explain the mechanism behind the lemma. For an edge e = { u , v } e=\{u,v\} e = { u , v } , define its cyclic length by
ℓ ( e ) = min { ( v − u ) m o d n , ( u − v ) m o d n } . \ell(e)=\min\{(v-u)\mathbin{\mathrm{mod}} n,(u-v)\mathbin{\mathrm{mod}} n\}. ℓ ( e ) = min {( v − u ) mod n , ( u − v ) mod n } .
Rotations preserve cyclic length. From J 1 J_1 J 1 , one can retain a linear-sized submatching F F F containing at most one edge of each non-antipodal cyclic length. Consequently, the translations
F s = ρ s ( F ) , s ∈ Z n , F_s=\rho_s(F), \qquad s\in\mathbb{Z}_n, F s = ρ s ( F ) , s ∈ Z n ,
are pairwise edge-disjoint. For a fixed shift s s s , a k k k -subset of F s F_s F s that is contained in J 2 J_2 J 2 is a certificate that the shift has overlap at least k k k . Counting these certificates over all shifts and applying a second-moment argument proves Theorem 5.3. The distinct-length reduction is precisely what makes the dependence between different shifts manageable; see Section C for the details.
The planted Hamilton-cycle model
Set q = d − 2 q=d-2 q = d − 2 . For each i = 1 , 2 i=1,2 i = 1 , 2 , independently sample a uniform Hamilton cycle H i H_i H i on [ n ] [n] [ n ] and an independent uniform simple q q q -regular graph R i R_i R i on [ n ] [n] [ n ] . Define
D i : = { E ( H i ) ∩ E ( R i ) = ∅ } . D_i:=\{E(H_i)\cap E(R_i)=\varnothing\}. D i := { E ( H i ) ∩ E ( R i ) = ∅ } .
Conditionally on D i D_i D i , the union
G i = H i ∪ R i G_i=H_i\cup R_i G i = H i ∪ R i
is a simple d d d -regular graph. Denote by Q ^ n , d \widehat{Q}_{n,d} Q n , d the law of the marked pair ( G i , H i ) (G_i,H_i) ( G i , H i ) after conditioning on D i D_i D i , and by Q n , d Q_{n,d} Q n , d its unmarked graph marginal. By Theorem 2.2 ,
Q n , d ≈ U n , d . Q_{n,d}\approx U_{n,d}. Q n , d ≈ U n , d .
We now prove the main existence result.
Proof of Theorem 5.1. Let
k = ⌊ ( 1 − ε ) log n log log n ⌋ . k=\left\lfloor(1-\varepsilon)\frac{\log n}{\log\log n}\right\rfloor. k = ⌊ ( 1 − ε ) log log n log n ⌋ .
We first work before conditioning on D 1 , D 2 D_1,D_2 D 1 , D 2 . Choose a cyclic ordering of each H i H_i H i , using only H i H_i H i , and identify its vertices with Z n \mathbb{Z}_n Z n . Conditional on H 1 , H 2 H_1,H_2 H 1 , H 2 , the residual graphs R 1 , R 2 R_1,R_2 R 1 , R 2 remain independent uniform simple q q q -regular graphs, since they are independent of the planted cycles and their laws are invariant under vertex permutations.
By the uniform matching-extraction lemma in Section C, from each R i R_i R i we may choose a matching
J i ⊆ E ( R i ) , ∣ J i ∣ = ⌊ n / 4 ⌋ , J_i\subseteq E(R_i), \qquad|J_i|=\lfloor n/4\rfloor, J i ⊆ E ( R i ) , ∣ J i ∣ = ⌊ n /4 ⌋ ,
such that J i J_i J i is marginally uniform among all matchings of that size. The two extracted matchings can be chosen independently. Theorem 5.3 therefore yields
P ( max s ∈ Z n ∣ ρ s ( J 1 ) ∩ J 2 ∣ ≥ k ) ⟶ 1. \mathbb{P}\left(\max_{s\in\mathbb{Z}_n}|\rho_s(J_1)\cap J_2|\ge k\right)\longrightarrow1. P ( s ∈ Z n max ∣ ρ s ( J 1 ) ∩ J 2 ∣ ≥ k ) ⟶ 1.
Since J i ⊆ E ( R i ) J_i\subseteq E(R_i) J i ⊆ E ( R i ) ,
P ( max s ∈ Z n ∣ ρ s ( E ( R 1 ) ) ∩ E ( R 2 ) ∣ ≥ k ) ⟶ 1. (16) \mathbb{P}\left(\max_{s\in\mathbb{Z}_n}|\rho_s(E(R_1))\cap E(R_2)|\ge k\right)\longrightarrow1. \tag*{(16)} P ( s ∈ Z n max ∣ ρ s ( E ( R 1 )) ∩ E ( R 2 ) ∣ ≥ k ) ⟶ 1. (16)
The edge-disjointness lemma in Section C gives, uniformly in the planted Hamilton cycles,
P ( D i ) ⟶ e − q , \mathbb{P}(D_i) \longrightarrow e^{-q}, P ( D i ) ⟶ e − q ,
and hence
P ( D 1 ∩ D 2 ) ⟶ e − 2 q > 0. \mathbb{P}(D_1 \cap D_2) \longrightarrow e^{-2q} > 0. P ( D 1 ∩ D 2 ) ⟶ e − 2 q > 0.
If B B B denotes the failure event in (16), then
P ( B ∣ D 1 ∩ D 2 ) ≤ P ( B ) P ( D 1 ∩ D 2 ) = o ( 1 ) . \mathbb{P}(B \mid D_1 \cap D_2) \le\frac{\mathbb{P}(B)}{\mathbb{P}(D_1 \cap D_2)} = o(1). P ( B ∣ D 1 ∩ D 2 ) ≤ P ( D 1 ∩ D 2 ) P ( B ) = o ( 1 ) .
Thus the residual surplus survives the conditioning.
Under D 1 ∩ D 2 D_1 \cap D_2 D 1 ∩ D 2 , identify both distinguished Hamilton cycles with
C n = { { x , x + 1 } : x ∈ Z n } . C_n = \{\{x,x+1\}: x \in\mathbb{Z}_n\}. C n = {{ x , x + 1 } : x ∈ Z n } .
Every rotation preserves C n C_n C n , and the residual edges are disjoint from C n C_n C n . Therefore, for every s s s ,
∣ ρ s ( E ( G 1 ) ) ∩ E ( G 2 ) ∣ = n + ∣ ρ s ( E ( R 1 ) ) ∩ E ( R 2 ) ∣ . \lvert\rho_s(E(G_1)) \cap E(G_2) \rvert= n + \lvert\rho_s(E(R_1)) \cap E(R_2) \rvert. ∣ ρ s ( E ( G 1 )) ∩ E ( G 2 )∣ = n + ∣ ρ s ( E ( R 1 )) ∩ E ( R 2 )∣ .
Consequently, under the marked planted law Q ^ n , d ⊗ 2 \widehat{\mathbb{Q}}_{n,d}^{\otimes2} Q n , d ⊗ 2 , with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) the distinguished pair of Hamilton cycles admits a cyclic alignment with overlap at least n + k n+k n + k .
It remains to forget the distinguished cycles. Consider the unmarked failure event that no pair of Hamilton cycles in G 1 , G 2 G_1,G_2 G 1 , G 2 admits a cyclic alignment with overlap at least n + k n+k n + k . Under Q n , d ⊗ 2 \mathbb{Q}_{n,d}^{\otimes2} Q n , d ⊗ 2 this event has probability o ( 1 ) o(1) o ( 1 ) , since the distinguished planted pair already succeeds with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Mutual contiguity, preserved under finite products, now gives the same conclusion under U n , d ⊗ 2 \mathbb{U}_{n,d}^{\otimes2} U n , d ⊗ 2 . This proves the theorem. □
The stronger Theorem 5.2 follows from the same marked planted law. The additional observation is that, conditional on the unmarked graph G G G , the distinguished planted Hamilton cycle is uniform among all Hamilton cycles of G G G . This turns the failure probability for the distinguished pair into the conditional proportion of bad Hamilton-cycle pairs. We give the short formal argument in Section C.
Sharpness of the cyclic-shift scale
For completeness, we record that the scale in Theorem 5.3 is sharp at first order. This is not needed for Theorem 5.1, but it identifies the natural limitation of the random-matching mechanism used above.
Proposition 5.4 (Cyclic overlap of random matchings). Fix c ∈ ( 0 , 1 / 2 ] c \in(0,1/2] c ∈ ( 0 , 1/2 ] . Let J 1 , J 2 J_1,J_2 J 1 , J 2 be independent uniform matchings of sizes a 1 , a 2 a_1,a_2 a 1 , a 2 satisfying
c n ≤ a i ≤ n / 2. cn \le a_i \le n/2. c n ≤ a i ≤ n /2. With
T n : = max s ∈ Z n ∣ ρ s ( J 1 ) ∩ J 2 ∣ , T_n := \max_{s \in\mathbb{Z}_n} \lvert\rho_s(J_1) \cap J_2 \rvert, T n := s ∈ Z n max ∣ ρ s ( J 1 ) ∩ J 2 ∣ , we have
T n log n / log log n → P 1 , \frac{T_n}{\log n/\log\log n} \xrightarrow{\mathbb{P}} 1, log n / log log n T n P 1 , uniformly over the allowed matching sizes.
The lower bound is Theorem 5.3; the matching upper tail is a direct first-moment estimate. We defer the proof to Section C. The same estimate applies to unions of a fixed number of independent perfect matchings and yields Theorem 1.6 ; its proof is recorded there as well.
A lower bound from cycle factors
The Hamilton-cycle argument of § 5 starts from a spanning cycle and uses contiguity to expose a tractable random residual graph. In principle, one could proceed similarly with k k k -cycle factors: Kahn–Lubetzky–Wormald prove contiguity for the corresponding planted model in the cubic case [13 ] , and state that their argument extends to every fixed degree d ≥ 3 d \ge3 d ≥ 3 . Such an approach would allow one to study the residual graph of a particular factor and then transfer the resulting graph event to the uniform model.
Here, we use a different mechanism. Near the cycle factor existence threshold, the family of relevant factors is small enough that the residual properties needed for the alignment can be proved simultaneously for every factor contained in the graph. More precisely, the expected number of realised factors is only exp ( o ( n ) ) \exp(o(n)) exp ( o ( n )) , whereas for a fixed realised factor the relevant residual-density estimate fails with probability exp ( − Θ ( n ) ) \exp(-\Theta(n)) exp ( − Θ ( n )) . This makes it possible to apply a union-bound over the entire family and then choose a factor after observing the graph. Recall
a d : = log ( d − 1 ) + d − 2 2 log ( d − 2 d ) . a_d := \log(d-1) + \frac{d-2}{2}\log\left(\frac{d-2}{d}\right). a d := log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) .
We first prove the result under k ∣ n k \mid n k ∣ n , and later remove the divisibility condition.
Theorem 6.1 (Cycle-factor surplus). Fix d ≥ 3 d \ge3 d ≥ 3 and ε > 0 \varepsilon> 0 ε > 0 . Let k = k ( n ) k = k(n) k = k ( n ) satisfy
k ∣ n , k = log n a d + o ( log n ) , k ≥ log n a d + log n . (17) k \mid n,\qquad k = \frac{\log n}{a_d} + o(\log n),\qquad k \ge\frac{\log n}{a_d} + \sqrt{\log n}. \tag*{(17)} k ∣ n , k = a d log n + o ( log n ) , k ≥ a d log n + log n . (17) If G 1 , G 2 G_1,G_2 G 1 , G 2 are independent uniform simple d d d -regular graphs on [ n ] [n] [ n ] , then
P ( M n ≥ n + ( 1 − ε ) n k ) ⟶ 1. \mathbb{P}\left(M_n \ge n + (1-\varepsilon)\frac{n}{k}\right) \longrightarrow1. P ( M n ≥ n + ( 1 − ε ) k n ) ⟶ 1.
The proof of the latter theorem follows three conceptual steps.
Control factors simultaneously. Theorem 2.3 gives only exp ( o ( n ) ) \exp(o(n)) exp ( o ( n )) realized factors in expectation at the scale (17). Conditional on one realised factor, the unused half-edges form a uniform ( d − 2 ) (d-2) ( d − 2 ) -regular pairing. An exponentially small concentration bound can therefore be union-bounded over all factors and all large unions of their cycles.
Build common stars. The resulting residual density guarantees a factor cycle with linearly many attachment positions. A suitable rotation aligns many attachment positions of two centre cycles, while a local-sparsity estimate lets us choose t t t distinct leaves on both sides. A star using t + 1 t+1 t + 1 factor cycles preserves all factor edges and gains t t t additional common residual edges.
Iterate. Repeating the star construction while a positive fraction of factor cycles remains gives asymptotically one additional common edge per factor cycle. Since q = ( a d + o ( 1 ) ) n / log n q=(a_d+o(1))n/\log n q = ( a d + o ( 1 )) n / log n , this yields the required surplus in the divisible case.
Uniform control over all short cycle factors
Put q : = n k q := \frac{n}{k} q := k n . In the configuration model, a realised k k k -cycle factor records both the abstract labelled factor and the particular half-edge pairs realising its n n n edges. If Y Y Y denotes the number of realized factors, Theorem 2.3 gives
log E [ Y ] = n a d − n k log ( 2 n / e ) + O d ( log n ) = o ( n ) , (18) \log\mathbb{E}[Y] = nad - \frac{n}{k}\log(2n/e) + O_d(\log n) = o(n), \tag*{(18)} log E [ Y ] = na d − k n log ( 2 n / e ) + O d ( log n ) = o ( n ) , (18)
where the last equality follows from (17) . Thus
E [ Y ] = exp ( o ( n ) ) . \mathbb{E}[Y] = \exp(o(n)). E [ Y ] = exp ( o ( n )) .
This subexponential count is the key feature that allows us to work uniformly over all realised factors, rather than with a distinguished planted factor. Let F F F be a k k k -cycle factor of a simple d d d -regular graph G G G , and write
R : = G ∖ E ( F ) R := G \setminus E(F) R := G ∖ E ( F )
for the graph containing its residual edges. We shall use the following two properties.
Property A (local sparsity). There is a constant J = J d J = J_d J = J d such that every vertex set S S S with ∣ S ∣ ≤ 2 k |S| \le2k ∣ S ∣ ≤ 2 k spans at most ∣ S ∣ + J |S| + J ∣ S ∣ + J edges in G G G .
Property B(η \eta η ) (residual density on large unions). For every union U U U of cycles of F F F with ∣ U ∣ ≥ η n |U| \ge\eta n ∣ U ∣ ≥ η n ,
e R ( U ) ≥ ( d − 2 ) ∣ U ∣ 2 4 n . e_R(U) \ge\frac{(d-2)|U|^2}{4n}. e R ( U ) ≥ 4 n ( d − 2 ) ∣ U ∣ 2 .
Property A has two consequences that will be used repeatedly. A single factor cycle contains at most J J J residual edges internally, and any two distinct factor cycles have at most J J J residual edges between them: in the latter case, apply Property A to their union, which has 2 k 2k 2 k vertices and already contains exactly 2 k 2k 2 k factor edges.
Proposition 6.2 (Uniformly good short cycle factors). Fix d ≥ 3 d \ge3 d ≥ 3 and η > 0 \eta> 0 η > 0 . Under (17) , with probability 1 − o ( 1 ) 1 - o(1) 1 − o ( 1 ) a uniform simple d d d -regular graph satisfies Property A and every k k k -cycle factor it contains satisfies Property B(η \eta η ).
Proof. The local-sparsity statement is proved in Theorem D.1 of Section D.
For Property B, fix a particular realised factor F F F in the configuration model. Conditional on the occurrence of its n n n prescribed factor pairs, the remaining ( d − 2 ) n (d-2)n ( d − 2 ) n half-edges are uniformly paired. Hence, for a fixed union U U U of factor cycles with ∣ U ∣ ≥ η n |U| \ge\eta n ∣ U ∣ ≥ η n , Theorem D.2 gives
P ( U violates Property B ( η ) ∣ F occurs ) ≤ e − c d , η n . \mathbb{P}(U\text{ violates Property B}(\eta) \mid F\text{ occurs}) \le e^{-c_{d,\eta}n}. P ( U violates Property B ( η ) ∣ F occurs ) ≤ e − c d , η n .
for some constant c d , η > 0 c_{d,\eta} > 0 c d , η > 0 . The factor has q q q cycles and therefore at most 2 q 2^q 2 q unions of cycles. Consequently,
P ( F is bad ∣ F occurs ) ≤ 2 q e − c d , η n . \mathbb{P}(F\text{ is bad} \mid F\text{ occurs}) \le2^q e^{-c_{d,\eta}n}. P ( F is bad ∣ F occurs ) ≤ 2 q e − c d , η n .
If Y b a d Y_{\mathrm{bad}} Y bad denotes the number of bad realised factors, summing this conditional estimate over all possible realised factors gives
E [ Y b a d ] ≤ ( E [ Y ] ) 2 q e − c d , η n . \mathbb{E}[Y_{\mathrm{bad}}] \le(\mathbb{E}[Y])2^q e^{-c_{d,\eta}n}. E [ Y bad ] ≤ ( E [ Y ]) 2 q e − c d , η n .
By (18) , E [ Y ] = e o ( n ) \mathbb{E}[Y] = e^{o(n)} E [ Y ] = e o ( n ) , while 2 q = e o ( n ) 2^q = e^{o(n)} 2 q = e o ( n ) because q = O ( n / log n ) q = O(n/\log n) q = O ( n / log n ) . Hence
E [ Y b a d ] ≤ e − c d , η n + o ( n ) = o ( 1 ) . \mathbb{E}[Y_{\mathrm{bad}}] \le e^{-c_{d,\eta}n+o(n)} = o(1). E [ Y bad ] ≤ e − c d , η n + o ( n ) = o ( 1 ) .
Markov’s inequality shows that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) in the configuration model, no realised factor is bad. Conditioning on simplicity preserves this high-probability statement, since the probability of simplicity tends to a positive constant. Combining it with Property A proves the proposition.
The point of Theorem 6.2 is that factor existence and factor regularity are now separated. Theorem 2.4 ensures that a factor exists, while the proposition says that whichever factor is selected afterwards already has the residual properties required by the alignment argument.
The deterministic common-star construction
We now forget randomness. Let G 1 , G 2 G_1,G_2 G 1 , G 2 be two simple d d d -regular graphs on n n n vertices, and suppose that each contains a k k k -cycle factor F i F_i F i satisfying Properties A and B(η \eta η ) with the same constants J J J and η \eta η . Call a factor cycle available if none of its vertices has yet been used. At every stage, the two graphs have the same number of available cycles.
Lemma 6.3 (A center with many attachment vertices). Suppose that m ≥ η q m \ge\eta q m ≥ η q cycles are available in one of the graphs. For all sufficiently large k k k , some available cycle contains at least η k / 4 \eta k/4 η k /4 distinct vertices having a residual edge to another available cycle.
Proof. Let U U U be the union of the m m m available cycles. Then ∣ U ∣ = m k ≥ η n |U|=mk \ge\eta n ∣ U ∣ = mk ≥ η n . Property B gives
e G ∖ F ( U ) ≥ ( d − 2 ) ∣ U ∣ 2 4 n . e_{G\setminus F}(U) \ge\frac{(d-2)|U|^2}{4n}. e G ∖ F ( U ) ≥ 4 n ( d − 2 ) ∣ U ∣ 2 .
By Property A, at most J m Jm J m residual edges lie internally inside the individual factor cycles. Hence, the number E c r o s s E_{\mathrm{cross}} E cross of residual edges joining two distinct available cycles satisfies, for all sufficiently large k k k ,
E c r o s s ≥ ( d − 2 ) ∣ U ∣ 2 4 n − J m ≥ ( d − 2 ) ∣ U ∣ 2 8 n . E_{\mathrm{cross}} \ge\frac{(d-2)|U|^2}{4n}-Jm \ge\frac{(d-2)|U|^2}{8n}. E cross ≥ 4 n ( d − 2 ) ∣ U ∣ 2 − J m ≥ 8 n ( d − 2 ) ∣ U ∣ 2 .
Summing the crossing degrees over the m m m available cycles counts every crossing edge twice. Therefore, some cycle is incident to at least
2 E c r o s s m ≥ ( d − 2 ) ∣ U ∣ k 4 n ≥ ( d − 2 ) η k 4 \frac{2E_{\mathrm{cross}}}{m} \ge\frac{(d-2)|U|k}{4n} \ge\frac{(d-2)\eta k}{4} m 2 E cross ≥ 4 n ( d − 2 ) ∣ U ∣ k ≥ 4 ( d − 2 ) η k
crossing residual edges. Each vertex has a residual degree at most d − 2 d-2 d − 2 , so at least η k / 4 \eta k/4 η k /4 distinct vertices of this cycle have a residual edge to another available cycle.
Lemma 6.4 (Common star). Fix η > 0 \eta>0 η > 0 and a positive integer t t t . For all sufficiently large k k k , whenever both graphs have at least η q \eta q η q available cycles, one can select t + 1 t+1 t + 1 available cycles in each graph and a bijection between their vertex sets that preserves all ( t + 1 ) k (t+1)k ( t + 1 ) k factor edges and at least t t t additional residual edges, one from a designated centre cycle to each of t t t distinct leaf cycles.
Proof. By Theorem 6.3, choose a centre cycle C i C_i C i in each graph such that at least η k / 4 \eta k/4 η k /4 of its vertices have a residual edge to another available cycle. Number the vertices of each centre cyclically by Z / k Z \mathbb{Z}/k\mathbb{Z} Z / k Z , and let A i A_i A i be the corresponding sets of attachment positions. Then
∣ A 1 ∣ , ∣ A 2 ∣ ≥ η k 4 . |A_1|,|A_2| \ge\frac{\eta k}{4}. ∣ A 1 ∣ , ∣ A 2 ∣ ≥ 4 η k .
Averaging over the k k k rotations gives
∑ s ∈ Z / k Z ∣ A 1 ∩ ( A 2 + s ) ∣ = ∣ A 1 ∣ ∣ A 2 ∣ . \sum_{s\in\mathbb{Z}/k\mathbb{Z}} |A_1 \cap(A_2+s)| = |A_1||A_2|. s ∈ Z / k Z ∑ ∣ A 1 ∩ ( A 2 + s ) ∣ = ∣ A 1 ∣∣ A 2 ∣.
Hence, some rotation of the identification of the two centres produces a set B B B of simultaneously good positions satisfying
∣ B ∣ ≥ ∣ A 1 ∣ ∣ A 2 ∣ k ≥ η 2 k 16 . (19) |B| \ge\frac{|A_1||A_2|}{k} \ge\frac{\eta^2 k}{16}. \tag*{(19)} ∣ B ∣ ≥ k ∣ A 1 ∣∣ A 2 ∣ ≥ 16 η 2 k . (19)
We now inductively choose t t t positions and t t t distinct leaf cycles. Suppose r < t r<t r < t leaves have already been selected in each graph. In graph i i i , call a position of B B B forbidden if its centre vertex is joined by a residual edge to one of those previously selected leaves. Property A bounds the number of residual edges between the centre and any fixed leaf by J J J . Thus, at most r J rJ r J positions are forbidden in either graph, and at most 2 r J 2rJ 2 r J positions are forbidden in at least one of them. Since t t t is fixed, for sufficiently large k k k ,
η 2 k 16 > 2 ( t − 1 ) J . \frac{\eta^2 k}{16} > 2(t-1)J. 16 η 2 k > 2 ( t − 1 ) J .
Therefore, a non-forbidden position remains. By the definition of B B B , the corresponding centre vertex has a residual edge to an available cycle in each graph; because the position is non-forbidden, neither leaf has been used before. Repeating this argument yields t t t distinct leaves on each side.
Map the centre cycles using the rotation selected above. For each chosen pair of leaves, choose the orientation and rotation of the second leaf so that the endpoint of the selected residual edge in G 1 G_1 G 1 maps to the corresponding endpoint in G 2 G_2 G 2 . These maps preserve all factor edges and the t t t selected centre-to-leaf residual edges. Since the chosen cycles are vertex-disjoint, the maps are compatible.
Lemma 6.5 (Iterating the stars). Under the deterministic assumptions above, for every fixed η > 0 \eta>0 η > 0 and positive integer t t t , and all sufficiently large n n n ,
M ( G 1 , G 2 ) ≥ n + t t + 1 ( 1 − η ) q − t . (20) M(G_1,G_2) \ge n+\frac{t}{t+1}(1-\eta)q-t. \tag*{(20)} M ( G 1 , G 2 ) ≥ n + t + 1 t ( 1 − η ) q − t . (20)
Proof. Start with all q q q factor cycles available. As long as at least η q \eta q η q cycles remain, apply Theorem 6.4, align one centre and t t t leaves, and remove those t + 1 t+1 t + 1 cycles from the available set in each graph. If a a a stages are completed and r = q − a ( t + 1 ) r=q-a(t+1) r = q − a ( t + 1 ) cycles remain, then at stopping r < η q r<\eta q r < η q , so
a = q − r t + 1 > ( 1 − η ) q t + 1 − 1. a=\frac{q-r}{t+1}>\frac{(1-\eta)q}{t+1}-1. a = t + 1 q − r > t + 1 ( 1 − η ) q − 1.
The maps constructed at different stages act on disjoint vertex sets. Pair and align the remaining factor cycles arbitrarily. The resulting permutation preserves all q k = n qk=n q k = n factor edges and gains t t t residual edges from each completed star. Hence
M ( G 1 , G 2 ) ≥ n + t a > n + t t + 1 ( 1 − η ) q − t , M(G_1,G_2)\ge n+ta>n+\frac{t}{t+1}(1-\eta)q-t, M ( G 1 , G 2 ) ≥ n + t a > n + t + 1 t ( 1 − η ) q − t ,
which proves (20).
The divisible case
Proof of Theorem 6.1. Fix η > 0 \eta> 0 η > 0 and a positive integer t t t . By Theorem 2.4 and (17), each graph contains a k k k -cycle factor with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . By Theorem 6.2, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) Property A holds and every such factor satisfies Property B(η \eta η ). Thus, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , each graph contains a factor to which Theorem 6.5 applies.
Since
q = n k = ( a d + o ( 1 ) ) n log n , q=\frac{n}{k}=(a_d+o(1))\frac{n}{\log n}, q = k n = ( a d + o ( 1 )) log n n ,
Theorem 6.5 yields
M ( G 1 , G 2 ) ≥ n + ( t t + 1 ( 1 − η ) a d − o ( 1 ) ) n log n . M(G_1,G_2)\ge n+\left(\frac{t}{t+1}(1-\eta)a_d-o(1)\right)\frac{n}{\log n}. M ( G 1 , G 2 ) ≥ n + ( t + 1 t ( 1 − η ) a d − o ( 1 ) ) log n n .
Equivalently,
M ( G 1 , G 2 ) ≥ n + ( t t + 1 ( 1 − η ) − o ( 1 ) ) n k . M(G_1,G_2)\ge n+\left(\frac{t}{t+1}(1-\eta)-o(1)\right)\frac{n}{k}. M ( G 1 , G 2 ) ≥ n + ( t + 1 t ( 1 − η ) − o ( 1 ) ) k n .
Given ε > 0 \varepsilon>0 ε > 0 , choose first η > 0 \eta>0 η > 0 small enough and then t t t large enough that
t t + 1 ( 1 − η ) > 1 − ε 2 . \frac{t}{t+1}(1-\eta)>1-\frac{\varepsilon}{2}. t + 1 t ( 1 − η ) > 1 − 2 ε .
These constants are fixed before n → ∞ n\to\infty n → ∞ , and Theorem 6.4 eventually applies because k → ∞ k\to\infty k → ∞ . The theorem follows.
The star construction gains asymptotically one residual common edge per factor cycle. This is why stars, rather than pairwise cycle matchings, recover the full coefficient a d a_d a d : grouping cycles only in pairs would yield roughly one extra edge for every two factor cycles and lose a factor two in the leading constant.
Removing the divisibility condition
The remaining issue is that the cycle-factor theorem is applied to a size N N N that is divisible by k k k , whereas the original graph size n n n is arbitrary, subject to d n dn d n being even. The following coupling is proved in Section D.
Lemma 6.6 (Size-reduction coupling). Fix d d d . Let N < n N<n N < n be admissible and suppose r : = n − N = O d ( log n ) r:=n-N=O_d(\log n) r := n − N = O d ( log n ) . There is a coupling of two independent graphs G 1 , G 2 ∼ U n , d G_1,G_2\sim\mathcal{U}_{n,d} G 1 , G 2 ∼ U n , d and two independent graphs H 1 , H 2 ∼ U N , d H_1,H_2\sim\mathcal{U}_{N,d} H 1 , H 2 ∼ U N , d such that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
M ( G 1 , G 2 ) ≥ M ( H 1 , H 2 ) − d r . (21) M(G_1,G_2)\ge M(H_1,H_2)-dr. \tag*{(21)} M ( G 1 , G 2 ) ≥ M ( H 1 , H 2 ) − d r . (21)
We can now prove the lower bound stated in the introduction.
Proof of Theorem 1.5. Fix ε > 0 \varepsilon>0 ε > 0 and choose ε 0 > 0 \varepsilon_0>0 ε 0 > 0 so small that
( 1 − ε 0 ) a d > a d − ε 3 . (1-\varepsilon_0)a_d>a_d-\frac{\varepsilon}{3}. ( 1 − ε 0 ) a d > a d − 3 ε .
Set
k = ⌊ log n a d + log n ⌋ . k=\left\lfloor\frac{\log n}{a_d}+\sqrt{\log n}\right\rfloor. k = ⌊ a d log n + log n ⌋ .
If d d d is odd, let L = lcm ( k , 2 ) L=\operatorname{lcm}(k,2) L = lcm ( k , 2 ) ; if d d d is even, let L = k L=k L = k . Let N N N be the largest multiple of L L L not exceeding n n n . Then d N dN d N is even, k ∣ N k\mid N k ∣ N , and
0 ≤ n − N < L ≤ 2 k = O d ( log n ) . 0\le n-N<L\le2k=O_d(\log n). 0 ≤ n − N < L ≤ 2 k = O d ( log n ) .
Since N = n − O d ( log n ) N=n-O_d(\log n) N = n − O d ( log n ) , we have
k = log N a d + o ( log N ) . k=\frac{\log N}{a_d}+o(\log N). k = a d log N + o ( log N ) .
Moreover, as N ≤ n N\le n N ≤ n and a d > 0 a_d>0 a d > 0 , our choice of k k k ensures that
k ≥ log n a d + log n ≥ log N a d + log N . k\ge\frac{\log n}{a_d}+\sqrt{\log n}\ge\frac{\log N}{a_d}+\sqrt{\log N}. k ≥ a d log n + log n ≥ a d log N + log N .
Thus, all the assumptions of Theorem 6.1 are satisfied, and applying that theorem with ε 0 \varepsilon_0 ε 0 gives
M ( H 1 , H 2 ) ≥ N + ( 1 − ε 0 ) N k = N + ( ( 1 − ε 0 ) a d − o ( 1 ) ) N log N . M(H_1,H_2)\ge N+(1-\varepsilon_0)\frac{N}{k}
=N+\bigl((1-\varepsilon_0)a_d-o(1)\bigr)\frac{N}{\log N}. M ( H 1 , H 2 ) ≥ N + ( 1 − ε 0 ) k N = N + ( ( 1 − ε 0 ) a d − o ( 1 ) ) log N N .
with high probability.
Apply Theorem 6.6. Since r = n − N = O d ( log n ) r=n-N=O_d(\log n) r = n − N = O d ( log n ) ,
M ( G 1 , G 2 ) ≥ N + ( ( 1 − ε 0 ) a d − o ( 1 ) ) N log N − d ( n − N ) = n + ( ( 1 − ε 0 ) a d − o ( 1 ) ) n log n , \begin{aligned}
M(G_1,G_2)&\ge N+\bigl((1-\varepsilon_0)a_d-o(1)\bigr)\frac{N}{\log N}-d(n-N)\\
&=n+\bigl((1-\varepsilon_0)a_d-o(1)\bigr)\frac{n}{\log n},
\end{aligned} M ( G 1 , G 2 ) ≥ N + ( ( 1 − ε 0 ) a d − o ( 1 ) ) log N N − d ( n − N ) = n + ( ( 1 − ε 0 ) a d − o ( 1 ) ) log n n ,
because n − N = o ( n / log n ) n-N=o(n/\log n) n − N = o ( n / log n ) and N / log N = ( 1 + o ( 1 ) ) n / log n N/\log N=(1+o(1))n/\log n N / log N = ( 1 + o ( 1 )) n / log n . By the choice of ε 0 \varepsilon_0 ε 0 , the last expression is at least
n + ( a d − ε ) n log n n+(a_d-\varepsilon)\frac{n}{\log n} n + ( a d − ε ) log n n
for all sufficiently large n n n , on an event of probability tending to one. This proves the theorem. □
The contrast with Section 5 can now be stated cleanly. For a fixed realised cycle factor, the residual pairing is uniform conditional on the factor, and the exponentially small probability of violating Property B can be summed over the entire near-threshold family because that family has only exp ( o ( n ) ) \exp(o(n)) exp ( o ( n )) members in expectation. The cycle factor may therefore be selected after observing the graph. In the Hamilton-cycle argument, we instead work with a distinguished planted cycle and use contiguity to transfer the resulting graph event.
Discussion and open questions
For every fixed d ≥ 3 d\ge3 d ≥ 3 , we have shown that the maximum overlap between two independent uniform d d d -regular graphs satisfies
( a d − o ( 1 ) ) n log n ≤ M n − n ≤ ( b d + o ( 1 ) ) n log n (a_d-o(1))\frac{n}{\log n}\le M_n-n\le(b_d+o(1))\frac{n}{\log n} ( a d − o ( 1 )) log n n ≤ M n − n ≤ ( b d + o ( 1 )) log n n
with high probability, where
a d = log ( d − 1 ) + d − 2 2 log ( d − 2 d ) , b d = d log ( d − 1 ) − ( d − 2 ) log ( d + 1 ) . a_d=\log(d-1)+\frac{d-2}{2}\log\left(\frac{d-2}{d}\right),\qquad b_d=d\log(d-1)-(d-2)\log(d+1). a d = log ( d − 1 ) + 2 d − 2 log ( d d − 2 ) , b d = d log ( d − 1 ) − ( d − 2 ) log ( d + 1 ) .
The two bounds arise from rather different arguments. The lower bound is produced by spanning cycle factors with cycle length of order log n \log n log n , together with a deterministic star construction that preserves asymptotically one additional residual edge per factor cycle. The upper bound instead comes from a first-moment count of common cores with minimum degree two, and is dominated by non-spanning witnesses. Understanding the gap between these two mechanisms is the main question left open by our results.
The Hamilton-cycle argument of § 5 illustrates a different, complementary mechanism. There, one starts with a distinguished spanning cycle, analyses the residual graph using a planted model, and transfers the resulting event via contiguity. For logarithmic cycle factors, the family of near-threshold factors is sufficiently small that the residual properties needed for the alignment can instead be established uniformly over all realised factors. This distinction between a planted distinguished structure and uniform control over an entire family of structures may be useful beyond the present problem.
Toward a sharp second-order constant. It is natural to ask whether there exists a deterministic constant γ d \gamma_d γ d such that
( M n − n ) log n n ⟶ P γ d . \frac{(M_n-n)\log n}{n} \overset{\mathbb{P}}{\longrightarrow} \gamma_d. n ( M n − n ) log n ⟶ P γ d .
On the lower-bound side, the current construction is naturally limited by the number of near-threshold factor cycles. If q = ( a d + o ( 1 ) ) n log n q=(a_d+o(1))\frac{n}{\log n} q = ( a d + o ( 1 )) l o g n n is the number of cycles in the factor, the quotient structure produced by the star construction is a forest and therefore contains at most q − 1 q-1 q − 1 residual edges. In this sense, the coefficient a d a_d a d is the natural endpoint of the present cycle-factor method. Improving it would require a common residual structure denser than a forest at the quotient level, or a different spanning decomposition.
The upper bound points to a different obstruction. In § 4 , the first moment for common cores is maximised by witnesses occupying asymptotically d n d + 1 \frac{dn}{d+1} d + 1 d n vertices. If one artificially restricted the count to spanning witnesses with minimum degree two, the same calculation would give the smaller coefficient 2 a d 2a_d 2 a d ; see (15) . In particular, the present union bound is limited by the entropy of non-spanning cores.
Beyond fixed-degree regular graphs. The present paper deliberately restricts its attention to fixed d d d . This assumption enters at several points: the simplicity probability of the configuration model remains bounded away from zero, the Hamiltonicity and cycle-factor inputs are stated for fixed degree, and all pairing estimates are used with constants that depend on d d d . It would therefore be interesting to investigate the regime d = d ( n ) → ∞ d=d(n)\to\infty d = d ( n ) → ∞ . Hamiltonicity is known to hold with high probability also for non-constant degrees in the range 3 ≤ d ≤ c n 3\le d\le cn 3 ≤ d ≤ c n , for a sufficiently small constant c > 0 c>0 c > 0 (see [5 ] ). The formulas above suggest that the second-order constants should grow like log d \log d log d , but the arguments given here are not uniform in d d d and do not identify the range of growth for which the scale n / log n n/\log n n / log n remains valid without modification.
A second natural direction is to replace regular graphs by configuration models with non-constant degree sequences. There are broad classes of such models, in particular under suitable assumptions with a minimum degree of at least three, for which Hamiltonicity holds with high probability [4 ] . This suggests that a Hamiltonian baseline may survive well beyond the regular case. The main difficulty is that the two ingredients used for the stronger lower bound become degree-dependent: one needs an analogue of the near-threshold logarithmic cycle-factor theorem, and after removing such a factor, the residual half-edge distribution is no longer regular. The constants governing both the factor threshold and the residual density should then depend on the underlying degree distribution. Developing a version of the present argument in that setting would provide a natural test of how much of the phenomenon is genuinely tied to regularity.
It is also useful to contrast the regular model with sparse Erdős–Rényi graphs. The methods of Sections 5 and 6 do not transfer directly to G ( n , c / n ) G(n,c/n) G ( n , c / n ) . In the regular model, the hard degree constraint provides a spanning Hamiltonian baseline and, after removing a spanning 2-factor, leaves a residual graph with a particularly tractable pairing structure. In sparse Erdős–Rényi graphs, low-degree and isolated vertices prevent such a spanning baseline in the same parameter range, and the residual graph obtained after exposing a spanning structure does not have the same regular-pairing form.
Algorithmic questions
The arguments in this paper are primarily information-theoretic. Once suitable short cycle factors satisfying the required residual properties are given, the deterministic star alignment from Section 6 is constructive: one repeatedly chooses a centre cycle with many residual attachments, tests the k = O ( log n ) k=O(\log n) k = O ( log n ) possible relative rotations of a pair of centres, and selects a fixed number of distinct leaves. The non-constructive step in the present proof is the production of a near-threshold spanning k k k -cycle factor in a typical random regular graph.
This suggests a natural algorithmic version of the problem: find, with high probability and in polynomial time, an alignment achieving a surplus of order n / log n n/\log n n / log n , ideally with an explicit constant. In this regime, multiplicative approximation of the total overlap is not the most informative objective, since the Hamiltonian baseline already contributes n n n common edges while the optimal improvement is only of order n / log n n/\log n n / log n . The appropriate algorithmic target is therefore the additive surplus above the baseline.
Acknowledgements
The authors are partially funded by the MUR (Italy) Department of Excellence 2023–2027.
Conflict of interest
None to declare.
Data availability
No datasets were generated or analysed in this theoretical study.
AI usage statement
This project fully aligns with the European Commission’s ERA Living Guidelines on the Responsible Use of Generative AI in Research (October 2026). The authors disclose the use of ChatGPT6 (OpenAI) and Grammarly during the preparation of this manuscript, for language editing, to improve exposition, and to organise mathematical arguments.
In particular, ChatGPT6 assisted in identifying and resolving an issue in the proof of the upper bound in Theorem 1.2 , arising from difficulties in applying a subset-sum estimate of Brito et al. It also suggested two improvements to the leading order constant of Theorems 1.4 and 1.5 : a slight refinement of the upper bound, and a more substantial improvement of the lower-bound constant by a factor of two. The latter was achieved by replacing an earlier contiguity-based approach with the actual argument described in § 6 .
All such mathematical arguments were subsequently developed, independently checked and verified by the authors, who take full responsibility for the statements, proofs, and conclusions of the manuscript.
Common subset sums of Ewens partitions
In this section, we prove the following lemma.
Lemma A.1 (Common subset sums). Let G 1 , G 2 G_1, G_2 G 1 , G 2 be independent samples from U n , 2 \mathsf{U}_{n,2} U n , 2 , and let L i \mathcal{L}_i L i be the set of all subset sums of the cycle lengths of G i G_i G i , including 0 0 0 and n n n . Then
∣ ( L 1 ∩ L 2 ) ∖ { 0 , n } ∣ = O P ( 1 ) . \left|(\mathcal{L}_1 \cap\mathcal{L}_2) \setminus\{0,n\}\right| = O_{\mathrm{P}}(1). ∣ ( L 1 ∩ L 2 ) ∖ { 0 , n } ∣ = O P ( 1 ) .
Combining this result with (10) yields a sharper upper bound in the proof of Theorem 1.2 .
Recall that the cycle counts of a uniform simple 2-regular graph follow the Ewens sampling distribution with parameter θ = 1 / 2 \theta= 1/2 θ = 1/2 , conditioned on having no cycles of lengths 1 or 2. For background on the Ewens sampling formula and the Feller coupling, see [17 ] .
Our approach builds on the study of subset sums of Ewens cycle lengths; see [3 ] . We separate small and macroscopic subset sums. For small sums, the Feller coupling reduces the problem to the intersection of two independent Poisson sumsets, which we show to be almost surely finite. For macroscopic sums, a weighted generating-function argument shows that two independent Ewens partitions have no common subset sums with high probability. Together, these estimates yield the required tightness.
For a sequence x = ( x ℓ ) ℓ ≥ 1 x = (x_\ell)_{\ell\ge1} x = ( x ℓ ) ℓ ≥ 1 of non-negative integers, define its sumset by
L ( x ) : = { ∑ ℓ ≥ 1 ℓ a ℓ : 0 ≤ a ℓ ≤ x ℓ , with finite support } . \mathcal{L}(x) := \left\{\sum_{\ell\ge1} \ell a_\ell: 0 \le a_\ell\le x_\ell,\ \text{with finite support}\right\}. L ( x ) := { ℓ ≥ 1 ∑ ℓ a ℓ : 0 ≤ a ℓ ≤ x ℓ , with finite support } .
For a cycle-count vector C ( n ) C^{(n)} C ( n ) , the set L ( C ( n ) ) \mathcal{L}(C^{(n)}) L ( C ( n ) ) consists precisely of the integers that can be obtained by summing the lengths of a collection of cycles. Let Y = ( Y ℓ ) ℓ ≥ 1 Y = (Y_\ell)_{\ell\ge1} Y = ( Y ℓ ) ℓ ≥ 1 have independent coordinates with
Y ℓ ∼ Poi ( 1 2 ℓ ) . Y_\ell\sim\operatorname{Poi}\left(\frac{1}{2\ell}\right). Y ℓ ∼ Poi ( 2 ℓ 1 ) .
We first establish a property of the infinite sumsets that will be useful under the Feller coupling.
Lemma A.2. If Y ( 1 ) , Y ( 2 ) Y^{(1)},Y^{(2)} Y ( 1 ) , Y ( 2 ) are independent copies of Y Y Y , then
T : = ∣ L ( Y ( 1 ) ) ∩ L ( Y ( 2 ) ) ∣ < ∞ almost surely . T := \left|\mathcal{L}(Y^{(1)}) \cap\mathcal{L}(Y^{(2)})\right| < \infty\qquad\text{almost surely}. T := L ( Y ( 1 ) ) ∩ L ( Y ( 2 ) ) < ∞ almost surely .
Proof. Fix a = 11 / 20 a = 11/20 a = 11/20 . This choice satisfies
1 2 < a < min { 1 2 log 2 , 1 4 log ( 3 / 2 ) } , \frac{1}{2} < a < \min\left\{\frac{1}{2\log2},\frac{1}{4\log(3/2)}\right\}, 2 1 < a < min { 2 log 2 1 , 4 log ( 3/2 ) 1 } ,
as required by the summability estimates in the two parts of the argument. For m ≥ 1 m \ge1 m ≥ 1 put
N m = ∑ ℓ = 1 m Y ℓ , B m = [ z m ] ∏ ℓ = 1 m ( 1 + z ℓ ) Y ℓ . N_m = \sum_{\ell=1}^{m} Y_\ell,\qquad B_m = [z^m]\prod_{\ell=1}^{m}(1+z^\ell)^{Y_\ell}. N m = ℓ = 1 ∑ m Y ℓ , B m = [ z m ] ℓ = 1 ∏ m ( 1 + z ℓ ) Y ℓ .
Thus B m B_m B m counts the selections of available summands whose total is m m m , and m ∈ L ( Y ) m \in\mathcal{L}(Y) m ∈ L ( Y ) implies B m ≥ 1 B_m \ge1 B m ≥ 1 . Writing H m = ∑ ℓ = 1 m ℓ − 1 H_m = \sum_{\ell=1}^{m}\ell^{-1} H m = ∑ ℓ = 1 m ℓ − 1 , independence and the Poisson generating function give
E [ 2 − N m B m ] = [ z m ] ∏ ℓ = 1 m E [ ( 1 + z ℓ 2 ) Y ℓ ] = e − H m / 4 [ z m ] exp ( 1 4 ∑ ℓ = 1 m z ℓ ℓ ) = e − H m / 4 [ z m ] ( 1 − z ) − 1 / 4 = O ( m − 1 ) . \begin{aligned}
\mathbb{E}\left[2^{-N_m}B_m\right]
&= [z^m]\prod_{\ell=1}^{m}\mathbb{E}\left[\left(\frac{1+z^\ell}{2}\right)^{Y_\ell}\right] \\
&= e^{-H_m/4}[z^m]\exp\left(\frac{1}{4}\sum_{\ell=1}^{m}\frac{z^\ell}{\ell}\right) \\
&= e^{-H_m/4}[z^m](1-z)^{-1/4} = O(m^{-1}).
\end{aligned} E [ 2 − N m B m ] = [ z m ] ℓ = 1 ∏ m E [ ( 2 1 + z ℓ ) Y ℓ ] = e − H m /4 [ z m ] exp ( 4 1 ℓ = 1 ∑ m ℓ z ℓ ) = e − H m /4 [ z m ] ( 1 − z ) − 1/4 = O ( m − 1 ) .
The third equality holds because terms of degree greater than m m m do not affect the coefficient of z m z^m z m . On { N m ≤ a log m } \{N_m \le a\log m\} { N m ≤ a log m } , 2 − N m B m ≥ m − a log 2 2^{-N_m}B_m \ge m^{-a\log2} 2 − N m B m ≥ m − a l o g 2 whenever m ∈ L ( Y ) m \in\mathcal{L}(Y) m ∈ L ( Y ) . Hence
P ( m ∈ L ( Y ) , N m ≤ a log m ) ≤ C m − 1 + a log 2 . (22) \mathbb{P}(m \in\mathcal{L}(Y),\,N_m \le a\log m) \le C m^{-1+a\log2}. \tag*{(22)} P ( m ∈ L ( Y ) , N m ≤ a log m ) ≤ C m − 1 + a l o g 2 . (22)
By independence, the probability that m m m belongs to both sumsets and that both corresponding bounds on N m N_m N m hold is at most
C 2 m − 2 + 2 a log 2 . C^2m^{-2+2a\log2}. C 2 m − 2 + 2 a l o g 2 .
The sum of these probabilities over m ≥ 2 m \ge2 m ≥ 2 is finite, since 2 a log 2 < 1 2a\log2 < 1 2 a log 2 < 1 .
Finally, N m N_m N m has the same finite-dimensional distributions as a unit-rate Poisson process sampled at time H m / 2 H_m/2 H m /2 . Consequently N m / log m → 1 / 2 N_m/\log m \to1/2 N m / log m → 1/2 almost surely, and N m ≤ a log m N_m \le a\log m N m ≤ a log m eventually almost surely. The same holds for the independent copy. Borel–Cantelli applied to the summable probabilities above proves that only finitely many positive integers belong to both sumsets almost surely. Including 0 does not affect finiteness. □
Now, let C ( n ) = ( C 1 ( n ) , … , C n ( n ) ) C^{(n)} = (C_1^{(n)},\ldots,C_n^{(n)}) C ( n ) = ( C 1 ( n ) , … , C n ( n ) ) have the Ewens sampling distribution ESF( 1 / 2 , n ) (1/2,n) ( 1/2 , n ) , and set L n = L ( C ( n ) ) \mathcal{L}_n = \mathcal{L}(C^{(n)}) L n = L ( C ( n ) ) and κ n = ∑ ℓ = 1 n C ℓ ( n ) \kappa_n = \sum_{\ell=1}^{n} C_\ell^{(n)} κ n = ∑ ℓ = 1 n C ℓ ( n ) . For t > 0 t > 0 t > 0 and m ≥ 0 m \ge0 m ≥ 0 , define
h m ( t ) : = [ z m ] ( 1 − z ) − t / 2 = Γ ( m + t / 2 ) Γ ( t / 2 ) Γ ( m + 1 ) . h_m(t) := [z^m](1-z)^{-t/2} = \frac{\Gamma(m+t/2)}{\Gamma(t/2)\Gamma(m+1)}. h m ( t ) := [ z m ] ( 1 − z ) − t /2 = Γ ( t /2 ) Γ ( m + 1 ) Γ ( m + t /2 ) .
The Ewens sampling formula gives
P ( C ( n ) = c ) = 1 h n ( 1 ) ∏ ℓ = 1 n ( 1 / ( 2 ℓ ) ) c ℓ c ℓ ! , ∑ ℓ = 1 n ℓ c ℓ = n . \mathbb{P}(C^{(n)}=c) = \frac{1}{h_n(1)}\prod_{\ell=1}^{n}\frac{(1/(2\ell))^{c_\ell}}{c_\ell!}, \qquad\sum_{\ell=1}^{n}\ell c_\ell=n. P ( C ( n ) = c ) = h n ( 1 ) 1 ℓ = 1 ∏ n c ℓ ! ( 1/ ( 2 ℓ ) ) c ℓ , ℓ = 1 ∑ n ℓ c ℓ = n .
For 1 ≤ k ≤ n − 1 1 \le k \le n-1 1 ≤ k ≤ n − 1 , let A k A_k A k denote the number of collections of cycles whose total length is k k k , so that 1 { k ∈ L n } ≤ A k \mathbf{1}_{\{k\in\mathcal{L}_n\}} \le A_k 1 { k ∈ L n } ≤ A k . Marking the cycles selected by such a subset and those in its complement separately gives the exact identity
E [ A k t κ n ] = h k ( t ) h n − k ( t ) h n ( 1 ) . (23) \mathbb{E}[A_k t^{\kappa_n}] = \frac{h_k(t)h_{n-k}(t)}{h_n(1)}. \tag*{(23)} E [ A k t κ n ] = h n ( 1 ) h k ( t ) h n − k ( t ) . (23)
Lemma A.3. If L n ( 1 ) , L n ( 2 ) \mathcal{L}_n^{(1)},\mathcal{L}_n^{(2)} L n ( 1 ) , L n ( 2 ) arise from two independent ESF( 1 / 2 , n ) (1/2,n) ( 1/2 , n ) permutations, then
P ( ( L n ( 1 ) ∩ L n ( 2 ) ) ∩ [ ⌊ n ⌋ , n − ⌊ n ⌋ ] ≠ ∅ ) = o ( 1 ) . \mathbb{P}\left((\mathcal{L}_n^{(1)}\cap\mathcal{L}_n^{(2)})\cap[\lfloor\sqrt{n}\rfloor,n-\lfloor\sqrt{n}\rfloor]\ne\varnothing\right)=o(1). P ( ( L n ( 1 ) ∩ L n ( 2 ) ) ∩ [⌊ n ⌋ , n − ⌊ n ⌋] = ∅ ) = o ( 1 ) .
Proof. Again set a = 11 / 20 a=11/20 a = 11/20 , and let E n = { κ n ≤ a log n } E_n=\{\kappa_n\le a\log n\} E n = { κ n ≤ a log n } . The classical independent-Bernoulli representation of the total number of cycles under Ewens’ distribution implies
E [ κ n ] = 1 2 log n + O ( 1 ) , Var ( κ n ) = O ( log n ) , \mathbb{E}[\kappa_n]=\frac{1}{2}\log n+O(1), \qquad\operatorname{Var}(\kappa_n)=O(\log n), E [ κ n ] = 2 1 log n + O ( 1 ) , Var ( κ n ) = O ( log n ) ,
so P ( E n ) = 1 − o ( 1 ) \mathbb{P}(E_n)=1-o(1) P ( E n ) = 1 − o ( 1 ) by Chebyshev’s inequality.
Take t = 2 / 3 t=2/3 t = 2/3 . On E n E_n E n we have 1 E n ≤ t − a log n t κ n \mathbf{1}_{E_n}\le t^{-a\log n}t^{\kappa_n} 1 E n ≤ t − a l o g n t κ n . For 1 ≤ k ≤ n / 2 1\le k\le n/2 1 ≤ k ≤ n /2 , using (23) and the coefficient estimates h m ( 2 / 3 ) = O ( ( m + 1 ) − 2 / 3 ) h_m(2/3)=O((m+1)^{-2/3}) h m ( 2/3 ) = O (( m + 1 ) − 2/3 ) and h n ( 1 ) − 1 = O ( n 1 / 2 ) h_n(1)^{-1}=O(n^{1/2}) h n ( 1 ) − 1 = O ( n 1/2 ) , we obtain
P ( k ∈ L n , E n ) ≤ t − a log n E [ A k t κ n ] ≤ C n a log ( 3 / 2 ) − 1 / 6 k − 2 / 3 . (24) \begin{aligned}
\mathbb{P}(k\in\mathcal{L}_n,E_n)\le t^{-a\log n}\mathbb{E}[A_k t^{\kappa_n}] \\
&\le Cn^{a\log(3/2)-1/6}k^{-2/3}. \tag*{(24)}
\end{aligned} P ( k ∈ L n , E n ) ≤ t − a l o g n E [ A k t κ n ] ≤ C n a l o g ( 3/2 ) − 1/6 k − 2/3 . (24)
Here we used n − k ≥ n / 2 n-k\ge n/2 n − k ≥ n /2 , and the constant is independent of k k k and n n n . Let R = ⌊ n ⌋ R=\lfloor\sqrt{n}\rfloor R = ⌊ n ⌋ . By the independence of the two Ewens partitions and a union bound,
P ( ∃ k ∈ [ R , n / 2 ] : k ∈ L n ( 1 ) ∩ L n ( 2 ) , E n ( 1 ) ∩ E n ( 2 ) ) ≤ C n 2 a log ( 3 / 2 ) − 1 / 3 ∑ k = R ⌊ n / 2 ⌋ k − 4 / 3 ≤ C n 2 a log ( 3 / 2 ) − 1 / 2 = o ( 1 ) , \begin{aligned}
\mathbb{P}\left(\exists k\in[R,n/2]: k\in\mathcal{L}^{(1)}_n\cap\mathcal{L}^{(2)}_n,\ \mathcal{E}^{(1)}_n\cap\mathcal{E}^{(2)}_n\right) \\
&\le Cn^{2a\log(3/2)-1/3}\sum_{k=R}^{\lfloor n/2\rfloor} k^{-4/3} \\
&\le Cn^{2a\log(3/2)-1/2}=o(1),
\end{aligned} P ( ∃ k ∈ [ R , n /2 ] : k ∈ L n ( 1 ) ∩ L n ( 2 ) , E n ( 1 ) ∩ E n ( 2 ) ) ≤ C n 2 a l o g ( 3/2 ) − 1/3 k = R ∑ ⌊ n /2 ⌋ k − 4/3 ≤ C n 2 a l o g ( 3/2 ) − 1/2 = o ( 1 ) ,
because 2 a log ( 3 / 2 ) < 1 / 2 2a\log(3/2)<1/2 2 a log ( 3/2 ) < 1/2 . Finally, k ∈ L n k\in\mathcal{L}_n k ∈ L n if and only if n − k ∈ L n n-k\in\mathcal{L}_n n − k ∈ L n , since taking the complementary set of cycles preserves the Ewens partition. The estimate, therefore, extends to [ R , n − R ] [R,n-R] [ R , n − R ] . Adding P ( ( E n ( 1 ) ) c ∪ ( E n ( 2 ) ) c ) = o ( 1 ) \mathbb{P}((\mathcal{E}^{(1)}_n)^c\cup(\mathcal{E}^{(2)}_n)^c)=o(1) P (( E n ( 1 ) ) c ∪ ( E n ( 2 ) ) c ) = o ( 1 ) proves the lemma. □
We are now ready to conclude the proof of the main lemma.
Proof of Theorem A.1. First consider two independent Ewens partitions C ( n , 1 ) , C ( n , 2 ) C^{(n,1)},C^{(n,2)} C ( n , 1 ) , C ( n , 2 ) with parameter 1 / 2 1/2 1/2 ; write L n ( i ) = L ( C ( n , i ) ) \mathcal{L}^{(i)}_n=\mathcal{L}(C^{(n,i)}) L n ( i ) = L ( C ( n , i ) ) . Let R = ⌊ n ⌋ R=\lfloor\sqrt{n}\rfloor R = ⌊ n ⌋ .
By the Feller coupling (see [3 Section 3.1, Lemma 10] ), each C ( n , i ) C^{(n,i)} C ( n , i ) can be coupled to a sequence Y ( i ) Y^{(i)} Y ( i ) of independent Poi ( 1 / ( 2 ℓ ) ) \operatorname{Poi}(1/(2\ell)) Poi ( 1/ ( 2 ℓ )) variables in such a way that
C ℓ ( n , i ) ≤ Y ℓ ( i ) + 1 { J n ( i ) = ℓ } , 1 ≤ ℓ ≤ n , C^{(n,i)}_\ell\le Y^{(i)}_\ell+1_{\{J^{(i)}_n=\ell\}},\qquad1\le\ell\le n, C ℓ ( n , i ) ≤ Y ℓ ( i ) + 1 { J n ( i ) = ℓ } , 1 ≤ ℓ ≤ n ,
where the same reference gives, for ℓ < n \ell<n ℓ < n ,
P ( J n ( i ) = ℓ ) ≤ 1 2 ( n − ℓ ) . \mathbb{P}(J^{(i)}_n=\ell)\le\frac{1}{2(n-\ell)}. P ( J n ( i ) = ℓ ) ≤ 2 ( n − ℓ ) 1 .
Consequently,
P ( J n ( 1 ) ≤ R or J n ( 2 ) ≤ R ) ≤ ∑ i = 1 2 ∑ ℓ = 1 R 1 2 ( n − ℓ ) = O ( n − 1 / 2 ) . \mathbb{P}(J^{(1)}_n\le R\text{ or }J^{(2)}_n\le R)\le\sum_{i=1}^{2}\sum_{\ell=1}^{R}\frac{1}{2(n-\ell)}=O(n^{-1/2}). P ( J n ( 1 ) ≤ R or J n ( 2 ) ≤ R ) ≤ i = 1 ∑ 2 ℓ = 1 ∑ R 2 ( n − ℓ ) 1 = O ( n − 1/2 ) .
On the complementary event, for i = 1 , 2 i=1,2 i = 1 , 2 ,
L n ( i ) ∩ [ 0 , R ] ⊆ L ( Y ( i ) ) ∩ [ 0 , R ] , \mathcal{L}^{(i)}_n\cap[0,R]\subseteq\mathcal{L}(Y^{(i)})\cap[0,R], L n ( i ) ∩ [ 0 , R ] ⊆ L ( Y ( i ) ) ∩ [ 0 , R ] ,
since every subset sum at most R R R uses only cycles of length at most R R R . By Theorem A.3, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) there are no common subset sums in [ R , n − R ] [R,n-R] [ R , n − R ] . By symmetry around n / 2 n/2 n /2 , the number of remaining non-trivial common subset sums is at most
2 ∣ L ( Y ( 1 ) ) ∩ L ( Y ( 2 ) ) ∣ . 2\left|\mathcal{L}(Y^{(1)})\cap\mathcal{L}(Y^{(2)})\right|. 2 L ( Y ( 1 ) ) ∩ L ( Y ( 2 ) ) .
The quantity on the right is almost surely finite by Theorem A.2, and its law does not depend on n n n . This shows that
∣ ( L n ( 1 ) ∩ L n ( 2 ) ) ∖ { 0 , n } ∣ = O P ( 1 ) \left|(\mathcal{L}^{(1)}_n\cap\mathcal{L}^{(2)}_n)\setminus\{0,n\}\right|=O_{\mathbb{P}}(1) ( L n ( 1 ) ∩ L n ( 2 ) ) ∖ { 0 , n } = O P ( 1 )
for two independent Ewens partitions.
Finally, the cycle counts of a uniform simple 2-regular graph have exactly the ESF( 1 / 2 , n ) (1/2,n) ( 1/2 , n ) distribution conditioned on C 1 ( n ) = C 2 ( n ) = 0 C^{(n)}_1=C^{(n)}_2=0 C 1 ( n ) = C 2 ( n ) = 0 . The probability of this event tends to e − 3 / 4 > 0 e^{-3/4}>0 e − 3/4 > 0 by the convergence of the first two Ewens cycle counts to independent Poisson variables with means 1 / 2 1/2 1/2 and 1 / 4 1/4 1/4 . Conditioning two independent Ewens partitions on these two events thus preserves the O P ( 1 ) O_{\mathbb{P}}(1) O P ( 1 ) bound (at a bounded multiplicative cost in probabilities), and gives the statement for G 1 , G 2 ∼ U n , 2 G_1,G_2\sim\mathcal{U}_{n,2} G 1 , G 2 ∼ U n , 2 . □
Technical estimates for the upper bound
This appendix proves Theorem 4.3. We keep the notation of § 4 . Thus, v v v is the number of vertices of the common core, s s s is its excess, and
All estimates below are for fixed d ≥ 3 d \ge3 d ≥ 3 . We work first in the configuration model; conditioning on simplicity is performed only in the proof of Theorem 4.5 .
Configuration-model enumeration
Lemma B.1 (Counting common cores). For every feasible v v v and s s s ,
E Z v , s ≤ ( n v ) 2 v ! ( 2 m − 1 ) ! ! ( ( d n − 2 m − 1 ) ! ! ( d n − 1 ) ! ! ) 2 × ∑ a 1 , … , a v ∈ { 2 , … , d } ∑ i a i = 2 m ∏ i = 1 v ( d ) a i 2 a i ! . (25) \mathbb{E}Z_{v,s} \le\binom{n}{v}^{2} v!(2m-1)!!\left(\frac{(dn-2m-1)!!}{(dn-1)!!}\right)^{2}
\times\sum_{\substack{a_1,\ldots,a_v\in\{2,\ldots,d\}\\ \sum_i a_i=2m}}\prod_{i=1}^{v}\frac{(d)_{a_i}^{2}}{a_i!}. \tag*{(25)} E Z v , s ≤ ( v n ) 2 v ! ( 2 m − 1 )!! ( ( d n − 1 )!! ( d n − 2 m − 1 )!! ) 2 × a 1 , … , a v ∈ { 2 , … , d } ∑ i a i = 2 m ∑ i = 1 ∏ v a i ! ( d ) a i 2 . (25)
Here ( d ) r = d ( d − 1 ) ⋯ ( d − r + 1 ) (d)_r=d(d-1)\cdots(d-r+1) ( d ) r = d ( d − 1 ) ⋯ ( d − r + 1 ) .
Proof. Choose the two v v v -vertex sets and the bijection between them in
( n v ) 2 v ! \binom{n}{v}^{2}v! ( v n ) 2 v !
ways. Fix a degree sequence a 1 , … , a v ∈ { 2 , … , d } a_1,\ldots,a_v\in\{2,\ldots,d\} a 1 , … , a v ∈ { 2 , … , d } with sum 2 m 2m 2 m .
The number of simple labelled graphs with this degree sequence is at most
( 2 m − 1 ) ! ! ∏ i = 1 v a i ! . \frac{(2m-1)!!}{\prod_{i=1}^{v}a_i!}. ∏ i = 1 v a i ! ( 2 m − 1 )!! .
Indeed, attach a i a_i a i labelled auxiliary half-edges to vertex i i i and pair the resulting 2 m 2m 2 m half-edges. Every simple graph with the prescribed degree sequence is generated by exactly ∏ i a i ! \prod_i a_i! ∏ i a i ! such pairings, whereas pairings that produce loops or multiple edges only increase the upper bound.
Now fix one such simple graph H H H . At vertex i i i , the a i a_i a i incidences of H H H can be assigned injectively to the d d d configuration half-edges in ( d ) a i (d)_{a_i} ( d ) a i ways. Once all incidence assignments are fixed, the m m m edges of H H H prescribe m m m disjoint half-edge pairs. A uniform pairing of the d n dn d n half-edges contains these prescribed pairs with probability
( d n − 2 m − 1 ) ! ! ( d n − 1 ) ! ! . \frac{(dn-2m-1)!!}{(dn-1)!!}. ( d n − 1 )!! ( d n − 2 m − 1 )!! .
Consequently,
P ( H ⊆ G n , d C M ) ≤ ( ∏ i = 1 v ( d ) a i ) ( d n − 2 m − 1 ) ! ! ( d n − 1 ) ! ! . \mathbb{P}\left(H\subseteq G_{n,d}^{\mathrm{CM}}\right)\le\left(\prod_{i=1}^{v}(d)_{a_i}\right)\frac{(dn-2m-1)!!}{(dn-1)!!}. P ( H ⊆ G n , d CM ) ≤ ( i = 1 ∏ v ( d ) a i ) ( d n − 1 )!! ( d n − 2 m − 1 )!! .
The two configuration models are independent, and the image of H H H under the chosen bijection has the same degree sequence. Squaring the containment probability, multiplying by the graph count, and summing over all admissible degree sequences gives (25). ∎
The entropy of the degree sequence
The minimum-degree condition makes degree two the natural baseline. Write
a i = 2 + b i , 0 ≤ b i ≤ d − 2. a_i = 2 + b_i,\qquad0 \le b_i \le d - 2. a i = 2 + b i , 0 ≤ b i ≤ d − 2.
Since ∑ i a i = 2 v + 2 s \sum_i a_i = 2v + 2s ∑ i a i = 2 v + 2 s , the excess is encoded by
∑ i = 1 v b i = 2 s . \sum_{i=1}^{v} b_i = 2s. i = 1 ∑ v b i = 2 s .
Lemma B.2 (Degree-sequence entropy). Set
Λ d : = d 2 ( d − 1 ) 2 2 . \Lambda_d := \frac{d^2(d-1)^2}{2}. Λ d := 2 d 2 ( d − 1 ) 2 . Uniformly for 1 ≤ s ≤ n / 2 1 \le s \le n/2 1 ≤ s ≤ n /2 and 1 ≤ v ≤ n 1 \le v \le n 1 ≤ v ≤ n ,
∑ a 1 , … , a v ∈ { 2 , … , d } ∑ i a i = 2 v + 2 s ∏ i = 1 v ( d a i ) 2 a i ! ≤ Λ d v exp { O d ( s log n s + s ) } . (26) \sum_{\substack{a_1,\ldots,a_v\in\{2,\ldots,d\}\\ \sum_i a_i=2v+2s}}
\prod_{i=1}^{v}\frac{\binom{d}{a_i}^2}{a_i!}
\le\Lambda_d^v \exp\left\{O_d\left(s\log\frac{n}{s}+s\right)\right\}. \tag*{(26)} a 1 , … , a v ∈ { 2 , … , d } ∑ i a i = 2 v + 2 s ∑ i = 1 ∏ v a i ! ( a i d ) 2 ≤ Λ d v exp { O d ( s log s n + s ) } . (26)
Proof. For 0 ≤ b ≤ d − 2 0 \le b \le d-2 0 ≤ b ≤ d − 2 , put
w b : = ( d 2 + b ) 2 ( 2 + b ) ! . w_b := \frac{\binom{d}{2+b}^2}{(2+b)!}. w b := ( 2 + b )! ( 2 + b d ) 2 .
Then w 0 = Λ d w_0=\Lambda_d w 0 = Λ d . Since d d d is fixed, there is a constant C d ≥ 1 C_d\ge1 C d ≥ 1 such that
w b ≤ Λ d C d b , 0 ≤ b ≤ d − 2. w_b \le\Lambda_d C_d^b,\qquad0\le b\le d-2. w b ≤ Λ d C d b , 0 ≤ b ≤ d − 2.
Hence every admissible vector ( b 1 , … , b v ) (b_1,\ldots,b_v) ( b 1 , … , b v ) with sum 2 s 2s 2 s contributes at most
Λ d v C d 2 s . \Lambda_d^v C_d^{2s}. Λ d v C d 2 s .
Ignoring the upper bounds b i ≤ d − 2 b_i\le d-2 b i ≤ d − 2 can only increase the number of vectors. The number of nonnegative integer solutions to ∑ i b i = 2 s \sum_i b_i=2s ∑ i b i = 2 s is
( v + 2 s − 1 2 s ) ≤ ( e ( v + 2 s ) 2 s ) 2 s ≤ exp { O ( s log n s + s ) } , \binom{v+2s-1}{2s}
\le\left(\frac{e(v+2s)}{2s}\right)^{2s}
\le\exp\left\{O\left(s\log\frac{n}{s}+s\right)\right\}, ( 2 s v + 2 s − 1 ) ≤ ( 2 s e ( v + 2 s ) ) 2 s ≤ exp { O ( s log s n + s ) } ,
where we used v ≤ n v\le n v ≤ n and s ≤ n / 2 s\le n/2 s ≤ n /2 . Multiplying the two estimates proves (26).
The cost of positive excess
Define the excess-zero comparison term
A v : = ( n v ) 2 v ! ( 2 v − 1 ) ! ! ( ( d n − 2 v − 1 ) ! ! ( d n − 1 ) ! ! ) 2 Λ d v . (27) A_v := \binom{n}{v}^2 v!(2v-1)!!
\left(\frac{(dn-2v-1)!!}{(dn-1)!!}\right)^2\Lambda_d^v. \tag*{(27)} A v := ( v n ) 2 v ! ( 2 v − 1 )!! ( ( d n − 1 )!! ( d n − 2 v − 1 )!! ) 2 Λ d v . (27)
Lemma B.3 (One factor n − 1 n^{-1} n − 1 per unit of excess). If s = O ( n / log n ) s=O(n/\log n) s = O ( n / log n ) , then uniformly over feasible v v v ,
E Z v , s ≤ A v exp { − s log n + O d ( s log n s + s ) } . (28) \mathbb{E}Z_{v,s}\le A_v\exp\left\{-s\log n+O_d\left(s\log\frac{n}{s}+s\right)\right\}. \tag*{(28)} E Z v , s ≤ A v exp { − s log n + O d ( s log s n + s ) } . (28)
Proof. By Lemmas B.1 and B.2, it remains to compare the pairing factor for m = v + s m=v+s m = v + s with the corresponding factor for m = v m=v m = v . Their ratio is
( 2 ( v + s ) − 1 ) ! ! ( 2 v − 1 ) ! ! ( ( d n − 2 ( v + s ) − 1 ) ! ! ( d n − 2 v − 1 ) ! ! ) 2 = ∏ j = 0 s − 1 2 v + 2 j + 1 ( d n − 2 v − 2 j − 1 ) 2 . \frac{(2(v+s)-1)!!}{(2v-1)!!}\left(\frac{(dn-2(v+s)-1)!!}{(dn-2v-1)!!}\right)^2
= \prod_{j=0}^{s-1}\frac{2v+2j+1}{(dn-2v-2j-1)^2}. ( 2 v − 1 )!! ( 2 ( v + s ) − 1 )!! ( ( d n − 2 v − 1 )!! ( d n − 2 ( v + s ) − 1 )!! ) 2 = j = 0 ∏ s − 1 ( d n − 2 v − 2 j − 1 ) 2 2 v + 2 j + 1 .
For v ≤ n v\le n v ≤ n and s = O ( n / log n ) s=O(n/\log n) s = O ( n / log n ) , the numerator of every factor is O ( n ) O(n) O ( n ) , while
d n − 2 v − 2 j − 1 ≥ ( d − 2 ) n − O ( n / log n ) ≥ c d n dn-2v-2j-1\ge(d-2)n-O(n/\log n)\ge c_d n d n − 2 v − 2 j − 1 ≥ ( d − 2 ) n − O ( n / log n ) ≥ c d n
for some c d > 0 c_d>0 c d > 0 and all sufficiently large n n n . Hence, each factor is at most C d / n C_d/n C d / n , uniformly in v v v and j j j . The whole ratio is therefore at most
n − s e O d ( s ) . n^{-s}e^{O_d(s)}. n − s e O d ( s ) .
Combining this estimate with (26) proves (28).
Entropy of the excess-zero core
Lemma B.4 (Entropy of the core size). Let x = v / n x=v/n x = v / n . Uniformly for 1 ≤ v ≤ n 1\le v\le n 1 ≤ v ≤ n ,
log A v = n f d ( x ) + O d ( log n ) , (29) \log A_v=n f_d(x)+O_d(\log n), \tag*{(29)} log A v = n f d ( x ) + O d ( log n ) , (29)
where f d f_d f d is defined in (11).
Proof. Use
( 2 r − 1 ) ! ! = ( 2 r ) ! 2 r r ! . (2r-1)!!=\frac{(2r)!}{2^r r!}. ( 2 r − 1 )!! = 2 r r ! ( 2 r )! .
and Stirling’s formula in the form
log r ! = r log r − r + O ( log ( r + 1 ) ) . \log r!=r\log r-r+O(\log(r+1)). log r ! = r log r − r + O ( log ( r + 1 )) .
Uniformly for 1 ≤ v ≤ n 1\le v\le n 1 ≤ v ≤ n , with x = v / n x=v/n x = v / n ,
log [ ( n v ) 2 v ! ] = 2 n [ − x log x − ( 1 − x ) log ( 1 − x ) ] + x n log ( x n ) − x n + O ( log n ) , (30) \log\left[\binom{n}{v}^2v!\right]
=2n[-x\log x-(1-x)\log(1-x)]+xn\log(xn)-xn+O(\log n), \tag*{(30)} log [ ( v n ) 2 v ! ] = 2 n [ − x log x − ( 1 − x ) log ( 1 − x )] + x n log ( x n ) − x n + O ( log n ) , (30)
log ( 2 v − 1 ) ! ! = x n log ( 2 x n ) − x n + O ( log n ) . (31) \log(2v-1)!!=xn\log(2xn)-xn+O(\log n). \tag*{(31)} log ( 2 v − 1 )!! = x n log ( 2 x n ) − x n + O ( log n ) . (31)
For the ratio of double factorials, write
log ( d n − 2 v − 1 ) ! ! ( d n − 1 ) ! ! = − ∑ j = 0 v − 1 log ( d n − 2 j − 1 ) = − v log n − ∑ j = 0 v − 1 log ( d − 2 j + 1 n ) . \begin{aligned}
\log\frac{(dn-2v-1)!!}{(dn-1)!!}
=-\sum_{j=0}^{v-1}\log(dn-2j-1) \\
&=-v\log n-\sum_{j=0}^{v-1}\log\left(d-\frac{2j+1}{n}\right).
\end{aligned} log ( d n − 1 )!! ( d n − 2 v − 1 )!! = − j = 0 ∑ v − 1 log ( d n − 2 j − 1 ) = − v log n − j = 0 ∑ v − 1 log ( d − n 2 j + 1 ) .
Since d ≥ 3 d\ge3 d ≥ 3 , the function y ↦ log ( d − 2 y ) y\mapsto\log(d-2y) y ↦ log ( d − 2 y ) and its derivative are uniformly bounded on [ 0 , 1 ] [0,1] [ 0 , 1 ] . A Riemann-sum estimate therefore gives
log ( d n − 2 v − 1 ) ! ! ( d n − 1 ) ! ! = − x n log n − n ∫ 0 x log ( d − 2 y ) d y + O d ( 1 ) . (32) \log\frac{(dn-2v-1)!!}{(dn-1)!!}
=-xn\log n-n\int_0^x\log(d-2y)\,\mathrm{d}y+O_d(1). \tag*{(32)} log ( d n − 1 )!! ( d n − 2 v − 1 )!! = − x n log n − n ∫ 0 x log ( d − 2 y ) d y + O d ( 1 ) . (32)
The integral is
∫ 0 x log ( d − 2 y ) d y = 1 2 [ d log d − ( d − 2 x ) log ( d − 2 x ) − 2 x ] . (33) \int_{0}^{x} \log(d-2y)\,\mathrm{d}y = \frac{1}{2}\left[d\log d-(d-2x)\log(d-2x)-2x\right]. \tag*{(33)} ∫ 0 x log ( d − 2 y ) d y = 2 1 [ d log d − ( d − 2 x ) log ( d − 2 x ) − 2 x ] . (33)
Finally,
v log Λ d = x n log d 2 ( d − 1 ) 2 2 . v\log\Lambda_d = xn\log\frac{d^2(d-1)^2}{2}. v log Λ d = x n log 2 d 2 ( d − 1 ) 2 .
Substituting (30) –(33) into (27) , all n log n n\log n n log n terms cancel and the remaining terms simplify to
n [ − 2 ( 1 − x ) log ( 1 − x ) + 2 x log [ d ( d − 1 ) ] − d log d + ( d − 2 x ) log ( d − 2 x ) ] + O d ( log n ) , n\left[-2(1-x)\log(1-x)+2x\log[d(d-1)]-d\log d+(d-2x)\log(d-2x)\right]+O_d(\log n), n [ − 2 ( 1 − x ) log ( 1 − x ) + 2 x log [ d ( d − 1 )] − d log d + ( d − 2 x ) log ( d − 2 x ) ] + O d ( log n ) ,
which is exactly (29) .
□ \square □
Proof of Theorem 4.3. Combining Theorem B.3 with Theorem B.4 gives
log E Z v , s ≤ n f d ( v / n ) − s log n + O d ( s log n s + s + log n ) . \log\mathbb{E}Z_{v,s}\le n f_d(v/n)-s\log n+O_d\left(s\log\frac{n}{s}+s+\log n\right). log E Z v , s ≤ n f d ( v / n ) − s log n + O d ( s log s n + s + log n ) .
In the regime 1 ≤ s = O ( n / log n ) 1\le s=O(n/\log n) 1 ≤ s = O ( n / log n ) , the additive O d ( s ) O_d(s) O d ( s ) term is absorbed by
O d ( s log n s ) , O_d\left(s\log\frac{n}{s}\right), O d ( s log s n ) ,
for all sufficiently large n n n , because n / s → ∞ n/s\to\infty n / s → ∞ . This proves (12) .
□ \square □
Technical estimates for Hamilton-cycle alignments
This appendix contains the auxiliary matching estimates and second-moment calculations used in Section 5. We also give the formal proof of Theorem 5.2 and the upper bound needed for Theorem 5.4 and Theorem 1.6.
Fixed subgraphs, extracted matchings, and edge-disjointness
We first collect three elementary facts about uniform regular graphs.
Lemma C.1 (Fixed-subgraph containment). Fix q ≥ 1 q\ge1 q ≥ 1 and a positive integer j j j . Let F ⊆ ( [ n ] 2 ) F\subseteq\binom{[n]}{2} F ⊆ ( 2 [ n ] ) be a deterministic set of j j j distinct edges, and write r v = d F ( v ) r_v=d_F(v) r v = d F ( v ) . If r v ≤ q r_v\le q r v ≤ q for every vertex, then for R ∼ U n , q R\sim\mathcal{U}_{n,q} R ∼ U n , q ,
P ( F ⊆ E ( R ) ) = ( 1 + o ( 1 ) ) ∏ v = 1 n ( q ) r v ( q n ) j , \mathbb{P}(F\subseteq E(R))=(1+o(1))\frac{\prod_{v=1}^{n}(q)_{r_v}}{(qn)^j}, P ( F ⊆ E ( R )) = ( 1 + o ( 1 )) ( q n ) j ∏ v = 1 n ( q ) r v , uniformly over the choice of F F F . If some r v > q r_v>q r v > q , the containment probability is zero. In particular, if F F F is a matching of j j j edges, then
P ( F ⊆ E ( R ) ) = ( 1 + o ( 1 ) ) ( q n ) j . \mathbb{P}(F\subseteq E(R))=(1+o(1))\left(\frac{q}{n}\right)^j. P ( F ⊆ E ( R )) = ( 1 + o ( 1 )) ( n q ) j .
Proof. In the configuration model, the half-edges corresponding to the incidences of F F F can be assigned in ∏ v ( q ) r v \prod_v(q)_{r_v} ∏ v ( q ) r v ways. For each assignment, the probability that the resulting j j j prescribed pairs occur is
∏ t = 0 j − 1 1 q n − 2 t − 1 . \prod_{t=0}^{j-1}\frac{1}{qn-2t-1}. t = 0 ∏ j − 1 q n − 2 t − 1 1 .
Since j j j and q q q are fixed,
P ( F ⊆ E ( G n , q C M ) ) = ( 1 + o ( 1 ) ) Π v ( q ) r v ( q n ) j . \mathbb{P}\left(F \subseteq E\left(G_{n,q}^{\mathrm{CM}}\right)\right)=(1+o(1))\frac{\Pi_v(q)r_v}{(qn)^j}. P ( F ⊆ E ( G n , q CM ) ) = ( 1 + o ( 1 )) ( q n ) j Π v ( q ) r v .
Conditioning on simplicity preserves this asymptotic estimate for fixed prescribed subgraphs; see [18 ] . The matching case follows because exactly 2 j 2j 2 j vertices have degree one in F F F .
Lemma C.2 (Uniform matching extraction). Fix q ≥ 1 q \ge1 q ≥ 1 and let R ∼ U n , q R \sim\mathcal{U}_{n,q} R ∼ U n , q . Set a = ⌊ n / 4 ⌋ a=\lfloor n/4\rfloor a = ⌊ n /4 ⌋ . There exists a random matching J ⊆ E ( R ) J \subseteq E(R) J ⊆ E ( R ) such that ∣ J ∣ = a |J|=a ∣ J ∣ = a and J J J is uniformly distributed among all matchings of size a a a on [ n ] [n] [ n ] .
Proof. Every q q q -regular graph contains a matching of size at least n / 4 n/4 n /4 . Indeed, a greedy maximal matching selects one edge at a time and removes at most 2 q − 1 2q-1 2 q − 1 edges at each step. Since the graph has q n / 2 qn/2 q n /2 edges, the resulting matching has size at least
q n / 2 2 q − 1 ≥ n 4 . \frac{qn/2}{2q-1} \ge\frac{n}{4}. 2 q − 1 q n /2 ≥ 4 n .
Conditionally on R R R , choose uniformly a matching J ⊆ E ( R ) J \subseteq E(R) J ⊆ E ( R ) of size a a a . The law of R R R and the selection rule are invariant under every permutation of the vertices. Since the symmetric group acts transitively on matchings of a fixed size, the marginal distribution of J J J is uniform among all size-a a a matchings on [ n ] [n] [ n ] .
Lemma C.3 (Edge-disjointness of a 2-factor and a regular graph). Fix q ≥ 1 q \ge1 q ≥ 1 . Let F F F be any deterministic simple 2-factor on [ n ] [n] [ n ] and let R ∼ U n , q R \sim\mathcal{U}_{n,q} R ∼ U n , q be independent of F F F . Then
∣ E ( F ) ∩ E ( R ) ∣ → d Poisson ( q ) , |E(F) \cap E(R)| \xrightarrow{d} \operatorname{Poisson}(q), ∣ E ( F ) ∩ E ( R ) ∣ d Poisson ( q ) , uniformly over the choice of F F F . In particular,
P ( E ( F ) ∩ E ( R ) = ∅ ) ⟶ e − q > 0. \mathbb{P}(E(F) \cap E(R)=\varnothing) \longrightarrow e^{-q}>0. P ( E ( F ) ∩ E ( R ) = ∅ ) ⟶ e − q > 0.
Proof. Let Z = ∣ E ( F ) ∩ E ( R ) ∣ Z=|E(F) \cap E(R)| Z = ∣ E ( F ) ∩ E ( R ) ∣ and fix a positive integer j j j . Since F F F has exactly n n n edges and maximum degree two, the number of ordered j j j -tuples of distinct, pairwise vertex-disjoint edges of F F F is
n j + O j ( n j − 1 ) , n^j+O_j(n^{j-1}), n j + O j ( n j − 1 ) ,
uniformly over the choice of F F F . By Theorem C.1, the probability that any such tuple is contained in R R R is
( 1 + o ( 1 ) ) ( q n ) j . (1+o(1))\left(\frac{q}{n}\right)^j. ( 1 + o ( 1 )) ( n q ) j .
There are only O j ( n j − 1 ) O_j(n^{j-1}) O j ( n j − 1 ) remaining ordered tuples of distinct edges of F F F , and their containment probabilities are at most O q , j ( n − j ) O_{q,j}(n^{-j}) O q , j ( n − j ) , again by Theorem C.1, with probability zero whenever a prescribed degree exceeds q q q . Consequently,
E [ ( Z ) j ] = ( n j + O j ( n j − 1 ) ) ( 1 + o ( 1 ) ) ( q n ) j + O q , j ( n − 1 ) ⟶ q j . \mathbb{E}[(Z)_j]=\left(n^j+O_j(n^{j-1})\right)(1+o(1))\left(\frac{q}{n}\right)^j+O_{q,j}(n^{-1})\longrightarrow q^j. E [( Z ) j ] = ( n j + O j ( n j − 1 ) ) ( 1 + o ( 1 )) ( n q ) j + O q , j ( n − 1 ) ⟶ q j .
These are the factorial moments of a Poisson random variable with mean q q q , proving the claim.
We now prove Theorem 5.3. Throughout this subsection, vertices are identified with elements of Z n \mathbb{Z}_n Z n .
Lemma C.4 (Containment probability for a random matching). Let J J J be a uniform matching of size a a a on Z n \mathbb{Z}_n Z n , and let S S S be a fixed matching consisting of j j j edges. Then
P ( S ⊆ J ) = p j ( a ) : = 2 j ( a ) j ( n ) 2 j . \mathbb{P}\left(S \subseteq J\right)=p_j^{(a)}:=\frac{2^j(a)_j}{(n)_{2j}}. P ( S ⊆ J ) = p j ( a ) := ( n ) 2 j 2 j ( a ) j . In particular, if a ≥ c n a \ge cn a ≥ c n for some fixed c > 0 c>0 c > 0 , and j = o ( n ) j=o(\sqrt{n}) j = o ( n ) , then, writing λ a = 2 a / n , \lambda_a=2a/n, λ a = 2 a / n ,
p j ( a ) = ( λ a n ) j exp ( O ( j 2 n ) ) , p_j^{(a)}=\left(\frac{\lambda_a}{n}\right)^j\exp\left(O\left(\frac{j^2}{n}\right)\right), p j ( a ) = ( n λ a ) j exp ( O ( n j 2 ) ) , uniformly over $cn\le a\le n/2.
Proof. The number of matchings of size a a a on n n n vertices is
n ! ( n − 2 a ) ! 2 a a ! . \frac{n!}{(n-2a)!\,2^a a!}. ( n − 2 a )! 2 a a ! n ! . After prescribing the j j j edges of S S S , the remaining a − j a-j a − j edges form an arbitrary matching on the other n − 2 j n-2j n − 2 j vertices. Taking the ratio gives
p j ( a ) = 2 j ( a ) j ( n ) 2 j . p_j^{(a)}=\frac{2^j(a)_j}{(n)_{2j}}. p j ( a ) = ( n ) 2 j 2 j ( a ) j . Moreover,
p j ( a ) = ( λ a n ) j ∏ r = 0 j − 1 ( 1 − r / a ) ∏ r = 0 2 j − 1 ( 1 − r / n ) . p_j^{(a)}=\left(\frac{\lambda_a}{n}\right)^j
\frac{\prod_{r=0}^{j-1}(1-r/a)}
{\prod_{r=0}^{2j-1}(1-r/n)}. p j ( a ) = ( n λ a ) j ∏ r = 0 2 j − 1 ( 1 − r / n ) ∏ r = 0 j − 1 ( 1 − r / a ) . Since a ≥ c n a\ge cn a ≥ c n and j = o ( n ) j=o(\sqrt{n}) j = o ( n ) ,
log ( p j ( a ) ( λ a / n ) j ) = O ( j 2 / n ) , \log\left(\frac{p_j^{(a)}}{(\lambda_a/n)^j}\right)=O(j^2/n), log ( ( λ a / n ) j p j ( a ) ) = O ( j 2 / n ) , uniformly over the allowed values of a a a .
For an edge e = { u , v } e=\{u,v\} e = { u , v } , define its cyclic length by
ℓ ( e ) = min { ( v − u ) m o d n , ( u − v ) m o d n } . \ell(e)=\min\{(v-u)\bmod n,(u-v)\bmod n\}. ℓ ( e ) = min {( v − u ) mod n , ( u − v ) mod n } .
Thus ℓ ( e ) ∈ { 1 , … , n / 2 } \ell(e)\in\{1,\ldots,n/2\} ℓ ( e ) ∈ { 1 , … , n /2 } when n n n is even, and rotations preserve cyclic length.
Lemma C.5 (Linearly many distinct cyclic lengths). Fix c ∈ ( 0 , 1 / 2 ] c\in(0,1/2] c ∈ ( 0 , 1/2 ] , and let J J J be a uniform matching of size a a a on Z n \mathbb{Z}_n Z n , where
c n ≤ a ≤ n / 2. cn\le a\le n/2. c n ≤ a ≤ n /2. With probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , J J J contains a matching F F F satisfying
∣ F ∣ ≥ c n 4 , |F|\ge\frac{cn}{4}, ∣ F ∣ ≥ 4 c n , such that all edges of F F F have pairwise distinct cyclic lengths, none equal to n / 2 n/2 n /2 . Consequently, the rotations
F s : = ρ s ( F ) , s ∈ Z n , F_s:=\rho_s(F),\qquad s\in\mathbb{Z}_n, F s := ρ s ( F ) , s ∈ Z n , are pairwise edge-disjoint.
Proof. For 1 ≤ ℓ < n / 2 1 \le\ell< n/2 1 ≤ ℓ < n /2 , let N ℓ N_\ell N ℓ be the number of edges of cyclic length ℓ \ell ℓ contained in J J J . Select one edge of every represented length and denote the resulting matching by F F F . Thus
∣ F ∣ = m : = ∑ ℓ = 1 ⌊ n / 2 ⌋ − 1 1 { N ℓ > 0 } . |F| = m := \sum_{\ell=1}^{\lfloor n/2\rfloor-1} \mathbf{1}_{\{N_\ell>0\}}. ∣ F ∣ = m := ℓ = 1 ∑ ⌊ n /2 ⌋ − 1 1 { N ℓ > 0 } .
For each ℓ < n / 2 \ell< n/2 ℓ < n /2 , there are exactly n n n edges of length ℓ \ell ℓ , so Theorem C.4 gives
E [ N ℓ ] = n p 1 ( a ) = 2 a n − 1 . \mathbb{E}[N_\ell] = np_1^{(a)} = \frac{2a}{n-1}. E [ N ℓ ] = n p 1 ( a ) = n − 1 2 a .
Among the ( n 2 ) \binom{n}{2} ( 2 n ) pairs of candidate edges of length ℓ \ell ℓ , exactly n n n pairs share a vertex. Hence
E ( N ℓ 2 ) = ( ( n 2 ) − n ) p 2 ( a ) = 2 a ( a − 1 ) ( n − 1 ) ( n − 2 ) . \mathbb{E}\binom{N_\ell}{2} = \left(\binom{n}{2}-n\right)p_2^{(a)} = \frac{2a(a-1)}{(n-1)(n-2)}. E ( 2 N ℓ ) = ( ( 2 n ) − n ) p 2 ( a ) = ( n − 1 ) ( n − 2 ) 2 a ( a − 1 ) .
Using 1 { z > 0 } ≥ z − ( z 2 ) \mathbf{1}_{\{z>0\}} \ge z-\binom{z}{2} 1 { z > 0 } ≥ z − ( 2 z ) for every non-negative integer z z z ,
E [ m ] ≥ ⌊ n 2 ⌋ − 1 [ 2 a n − 1 − 2 a ( a − 1 ) ( n − 1 ) ( n − 2 ) ] ≥ c n 2 − O ( 1 ) . (34) \mathbb{E}[m] \ge\left\lfloor\frac{n}{2}\right\rfloor-1\left[\frac{2a}{n-1}-\frac{2a(a-1)}{(n-1)(n-2)}\right] \ge\frac{cn}{2}-O(1). \tag*{(34)} E [ m ] ≥ ⌊ 2 n ⌋ − 1 [ n − 1 2 a − ( n − 1 ) ( n − 2 ) 2 a ( a − 1 ) ] ≥ 2 c n − O ( 1 ) . (34)
To obtain concentration, generate J J J by taking a uniform permutation σ \sigma σ of Z n \mathbb{Z}_n Z n and pairing
( σ 1 , σ 2 ) , ( σ 3 , σ 4 ) , … , ( σ 2 a − 1 , σ 2 a ) . (\sigma_1,\sigma_2),(\sigma_3,\sigma_4),\ldots,(\sigma_{2a-1},\sigma_{2a}). ( σ 1 , σ 2 ) , ( σ 3 , σ 4 ) , … , ( σ 2 a − 1 , σ 2 a ) .
Let
Y i = E [ m ∣ σ 1 , … , σ i ] , 0 ≤ i ≤ n . Y_i=\mathbb{E}[m\mid\sigma_1,\ldots,\sigma_i],\qquad0\le i\le n. Y i = E [ m ∣ σ 1 , … , σ i ] , 0 ≤ i ≤ n .
After fixing σ 1 , … , σ i − 1 \sigma_1,\ldots,\sigma_{i-1} σ 1 , … , σ i − 1 , completions with σ i = x \sigma_i=x σ i = x and σ i = y \sigma_i=y σ i = y can be paired by transposing x x x and y y y . Such a transposition changes at most two matching edges, hence changes m m m by at most two. Thus ∣ Y i − Y i − 1 ∣ ≤ 2 |Y_i-Y_{i-1}|\le2 ∣ Y i − Y i − 1 ∣ ≤ 2 , and the Azuma–Hoeffding inequality (see [14 ] ) gives
P ( m ≤ E [ m ] − t ) ≤ exp ( − t 2 8 n ) . \mathbb{P}\left(m\le\mathbb{E}[m]-t\right)\le\exp\left(-\frac{t^2}{8n}\right). P ( m ≤ E [ m ] − t ) ≤ exp ( − 8 n t 2 ) .
By (34),
P ( m < c n / 4 ) = o ( 1 ) . \mathbb{P}(m<cn/4)=o(1). P ( m < c n /4 ) = o ( 1 ) .
Finally, suppose that ρ s ( e ) = ρ t ( f ) \rho_s(e)=\rho_t(f) ρ s ( e ) = ρ t ( f ) for e , f ∈ F e,f\in F e , f ∈ F . Rotations preserve cyclic length, so ℓ ( e ) = ℓ ( f ) \ell(e)=\ell(f) ℓ ( e ) = ℓ ( f ) ; by construction, this forces e = f e=f e = f . Hence ρ t − s ( e ) = e \rho_{t-s}(e)=e ρ t − s ( e ) = e . A non-zero rotation can fix an unordered edge only when the edge is antipodal, i.e. has length n / 2 n/2 n /2 , which was excluded. Therefore s = t s=t s = t . □
Proof of Theorem 5.3. Apply Theorem C.5 to J 1 J_1 J 1 . With probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , there exists a matching F ⊆ J 1 F\subseteq J_1 F ⊆ J 1 with
m : = ∣ F ∣ ≥ c n / 4 m:=|F|\ge cn/4 m := ∣ F ∣ ≥ c n /4
whose edges have distinct non-antipodal cyclic lengths. Condition on any such realisation and write
F s = ρ s ( F ) , s ∈ Z n . F_s=\rho_s(F),\qquad s\in\mathbb{Z}_n. F s = ρ s ( F ) , s ∈ Z n .
For a fixed rotation s s s , call a set S ⊆ F s S\subseteq F_s S ⊆ F s a k k k -witness if ∣ S ∣ = k |S|=k ∣ S ∣ = k and S ⊆ J 2 S\subseteq J_2 S ⊆ J 2 . Define
Z s = ∑ S ⊆ F s ∣ S ∣ = k 1 { S ⊆ J 2 } , Z = ∑ s ∈ Z n Z s . Z_s=\sum_{\substack{S\subseteq F_s\\|S|=k}}\mathbf{1}_{\{S\subseteq J_2\}},\qquad Z=\sum_{s\in\mathbb{Z}_n}Z_s. Z s = S ⊆ F s ∣ S ∣ = k ∑ 1 { S ⊆ J 2 } , Z = s ∈ Z n ∑ Z s .
Then Z > 0 Z>0 Z > 0 implies max s ∣ ρ s ( J 1 ) ∩ J 2 ∣ ≥ k \max_s|\rho_s(\mathcal{J}_1)\cap\mathcal{J}_2|\ge k max s ∣ ρ s ( J 1 ) ∩ J 2 ∣ ≥ k .
For brevity, write
p j = p ( a 2 ) , λ = 2 a 2 n ∈ [ 2 c , 1 ] . p_j=p^{(a_2)},\qquad\lambda=\frac{2a_2}{n}\in[2c,1]. p j = p ( a 2 ) , λ = n 2 a 2 ∈ [ 2 c , 1 ] .
By Theorem C.4,
μ : = E [ Z ] = n ( m k ) p k . \mu:=\mathbb{E}[Z]=n\binom{m}{k}p_k. μ := E [ Z ] = n ( k m ) p k .
We estimate the second moment by separating different and equal shifts.
Different shifts. Since F s ∩ F t = ∅ F_s\cap F_t=\varnothing F s ∩ F t = ∅ whenever s ≠ t s\ne t s = t , two witnesses from different shifts share no edges. Their union either consists of 2 k 2k 2 k disjoint edges, in which case its probability of being contained in J 2 \mathcal{J}_2 J 2 is p 2 k p_{2k} p 2 k , or contains two incident edges, in which case the probability is zero. Hence
∑ s ≠ t E [ Z s Z t ] ≤ n ( n − 1 ) ( m k ) 2 p 2 k . \sum_{s\ne t}\mathbb{E}[Z_sZ_t]\le n(n-1)\binom{m}{k}^{2}p_{2k}. s = t ∑ E [ Z s Z t ] ≤ n ( n − 1 ) ( k m ) 2 p 2 k .
and therefore
∑ s ≠ t E [ Z s Z t ] μ 2 ≤ ( 1 − 1 n ) p 2 k p k 2 = 1 + o ( 1 ) , (35) \frac{\sum_{s\ne t}\mathbb{E}[Z_sZ_t]}{\mu^2}
\le\left(1-\frac{1}{n}\right)\frac{p_{2k}}{p_k^2}=1+o(1), \tag*{(35)} μ 2 ∑ s = t E [ Z s Z t ] ≤ ( 1 − n 1 ) p k 2 p 2 k = 1 + o ( 1 ) , (35)
because k 2 / n = o ( 1 ) k^2/n=o(1) k 2 / n = o ( 1 ) .
The same shift. Fix s s s . Two k k k -subsets S , S ′ ⊆ F s S,S'\subseteq F_s S , S ′ ⊆ F s may share edges. Classifying them by r = ∣ S ∩ S ′ ∣ r=|S\cap S'| r = ∣ S ∩ S ′ ∣ gives
E [ Z s 2 ] = ( m k ) ∑ r = 0 k ( k r ) ( m − k k − r ) p 2 k − r . \mathbb{E}[Z_s^2]=\binom{m}{k}\sum_{r=0}^{k}\binom{k}{r}\binom{m-k}{k-r}p_{2k-r}. E [ Z s 2 ] = ( k m ) r = 0 ∑ k ( r k ) ( k − r m − k ) p 2 k − r .
For a fixed S S S , let
b r : = ( k r ) ( m − k k − r ) ( m k ) , b_r:=\frac{\binom{k}{r}\binom{m-k}{k-r}}{\binom{m}{k}}, b r := ( k m ) ( r k ) ( k − r m − k ) ,
so that a union bound gives
b r ≤ ( k r ) ( k m − k + 1 ) r . b_r\le\binom{k}{r}\left(\frac{k}{m-k+1}\right)^r. b r ≤ ( r k ) ( m − k + 1 k ) r .
Moreover, Theorem C.4 yields
p 2 k − r p k 2 ≤ ( n λ ) r exp ( O ( k 2 n ) ) . \frac{p_{2k-r}}{p_k^2}\le\left(\frac{n}{\lambda}\right)^r\exp\left(O\left(\frac{k^2}{n}\right)\right). p k 2 p 2 k − r ≤ ( λ n ) r exp ( O ( n k 2 ) ) .
Since m ≥ c n / 4 m\ge cn/4 m ≥ c n /4 and λ ≥ 2 c \lambda\ge2c λ ≥ 2 c , for large n n n ,
n λ ( m − k + 1 ) ≤ 4 c 2 . \frac{n}{\lambda(m-k+1)}\le\frac{4}{c^2}. λ ( m − k + 1 ) n ≤ c 2 4 .
Writing C = 4 / c 2 C=4/c^2 C = 4/ c 2 ,
∑ s E [ Z s 2 ] μ 2 = 1 n ∑ r = 0 k b r p 2 k − r p k 2 ≤ exp ( O ( k 2 / n ) ) n ∑ r = 0 k ( k r ) ( C k ) r = exp ( O ( k 2 / n ) ) n ( 1 + C k ) k . (36) \begin{aligned}
\frac{\sum_s\mathbb{E}[Z_s^2]}{\mu^2}
=\frac{1}{n}\sum_{r=0}^{k}b_r\frac{p_{2k-r}}{p_k^2} \\
&\le\frac{\exp\left(O\left(k^2/n\right)\right)}{n}\sum_{r=0}^{k}\binom{k}{r}(Ck)^r \\
&=\frac{\exp\left(O\left(k^2/n\right)\right)}{n}(1+Ck)^k. \tag*{(36)}
\end{aligned} μ 2 ∑ s E [ Z s 2 ] = n 1 r = 0 ∑ k b r p k 2 p 2 k − r ≤ n exp ( O ( k 2 / n ) ) r = 0 ∑ k ( r k ) ( C k ) r = n exp ( O ( k 2 / n ) ) ( 1 + C k ) k . (36)
For
k = ⌊ ( 1 − ε ) log n log log n ⌋ , k=\left\lfloor(1-\varepsilon)\frac{\log n}{\log\log n}\right\rfloor, k = ⌊ ( 1 − ε ) log log n log n ⌋ ,
we have
log ( ( 1 + C k ) k n ) = − log n + k log k + O ( k ) = ( − ε + o ( 1 ) ) log n , \log\left(\frac{(1+Ck)^k}{n}\right)=-\log n+k\log k+O(k)=(-\varepsilon+o(1))\log n, log ( n ( 1 + C k ) k ) = − log n + k log k + O ( k ) = ( − ε + o ( 1 )) log n ,
so the right-hand side of (36) tends to zero. Combining this with (35) ,
E [ Z 2 ] E [ Z ] 2 = 1 + o ( 1 ) , Var ( Z ) E [ Z ] 2 = o ( 1 ) . \frac{\mathbb{E}[Z^2]}{\mathbb{E}[Z]^2}=1+o(1),\qquad\frac{\operatorname{Var}(Z)}{\mathbb{E}[Z]^2}=o(1). E [ Z ] 2 E [ Z 2 ] = 1 + o ( 1 ) , E [ Z ] 2 Var ( Z ) = o ( 1 ) .
Chebyshev’s inequality gives P ( Z = 0 ) = o ( 1 ) \mathbb{P}(Z=0)=o(1) P ( Z = 0 ) = o ( 1 ) . The initial distinct-length event fails with probability o ( 1 ) o(1) o ( 1 ) by Theorem C.5, completing the proof.
Typical Hamilton-cycle pairs
We now formalise and prove Theorem 5.2. Fix ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and write
k n = ⌊ ( 1 − ε ) log n log log n ⌋ . k_n=\left\lfloor(1-\varepsilon)\frac{\log n}{\log\log n}\right\rfloor. k n = ⌊ ( 1 − ε ) log log n log n ⌋ .
For a graph G G G , let H ( G ) \mathcal{H}(G) H ( G ) denote its set of unoriented Hamilton cycles. Given graphs G 1 , G 2 G_1,G_2 G 1 , G 2 and a pair
( H 1 , H 2 ) ∈ H ( G 1 ) × H ( G 2 ) , (H_1,H_2)\in\mathcal{H}(G_1)\times\mathcal{H}(G_2), ( H 1 , H 2 ) ∈ H ( G 1 ) × H ( G 2 ) ,
call ( H 1 , H 2 ) (H_1,H_2) ( H 1 , H 2 ) good if, after choosing either relative orientation of the two cycles, some cyclic shift of the induced identification satisfies
∣ π ( E ( G 1 ) ) ∩ E ( G 2 ) ∣ ≥ n + k n . \left|\pi(E(G_1))\cap E(G_2)\right|\ge n+k_n. ∣ π ( E ( G 1 )) ∩ E ( G 2 ) ∣ ≥ n + k n .
Define
A n ( G 1 , G 2 ) : = # { ( H 1 , H 2 ) ∈ H ( G 1 ) × H ( G 2 ) : ( H 1 , H 2 ) is good } ∣ H ( G 1 ) ∣ ∣ H ( G 2 ) ∣ , A_n(G_1,G_2):=\frac{\#\{(H_1,H_2)\in\mathcal{H}(G_1)\times\mathcal{H}(G_2):(H_1,H_2)\text{ is good}\}}{|\mathcal{H}(G_1)||\mathcal{H}(G_2)|}, A n ( G 1 , G 2 ) := ∣ H ( G 1 ) ∣∣ H ( G 2 ) ∣ # {( H 1 , H 2 ) ∈ H ( G 1 ) × H ( G 2 ) : ( H 1 , H 2 ) is good } ,
with the convention A n ( G 1 , G 2 ) = 0 A_n(G_1,G_2)=0 A n ( G 1 , G 2 ) = 0 if either graph has no Hamilton cycle. Thus Theorem 5.2 is the statement
A n ( G 1 , G 2 ) → P 1. A_n(G_1,G_2)\xrightarrow{\mathbb{P}}1. A n ( G 1 , G 2 ) P 1.
Proof of Theorem 5.2. Use the marked planted law Q ^ n , d \widehat{\mathbb{Q}}_{n,d} Q n , d from Section 5.2, with unmarked graph marginal Q n , d \mathbb{Q}_{n,d} Q n , d . Conditional on the resulting graph G G G , the distinguished Hamilton cycle is uniform over H ( G ) \mathcal{H}(G) H ( G ) . Indeed, before conditioning, every pair ( H , R ) (H,R) ( H , R ) with H H H a Hamilton cycle and R R R a simple ( d − 2 ) (d-2) ( d − 2 ) -regular graph has the same probability. After conditioning on edge-disjointness, a fixed d d d -regular graph G G G and a Hamilton cycle H ⊆ G H\subseteq G H ⊆ G determine exactly one residual graph,
E ( R ) = E ( G ) ∖ E ( H ) . E(R)=E(G)\setminus E(H). E ( R ) = E ( G ) ∖ E ( H ) .
Hence
P ( H = H 0 ∣ G ) = 1 ∣ H ( G ) ∣ \mathbb{P}(H=H_0\mid G)=\frac{1}{|\mathcal{H}(G)|} P ( H = H 0 ∣ G ) = ∣ H ( G ) ∣ 1
for every H 0 ∈ H ( G ) H_0\in\mathcal{H}(G) H 0 ∈ H ( G ) . For two independent planted samples, the distinguished cycles are independent conditional on ( G 1 , G 2 ) (G_1,G_2) ( G 1 , G 2 ) . Set
B n : = 1 − A n . B_n := 1-A_n. B n := 1 − A n .
Under Q n , d ⊗ 2 \mathbb{Q}_{n,d}^{\otimes2} Q n , d ⊗ 2 , B n ( G 1 , G 2 ) B_n(G_1,G_2) B n ( G 1 , G 2 ) is exactly the conditional probability that the two distinguished Hamilton cycles form a bad pair. The proof of Theorem 5.1 showed that the distinguished pair is bad with probability o ( 1 ) o(1) o ( 1 ) . Therefore
E Q n , d ⊗ 2 [ B n ] = o ( 1 ) . \mathbb{E}_{\mathbb{Q}_{n,d}^{\otimes2}}[B_n] = o(1). E Q n , d ⊗ 2 [ B n ] = o ( 1 ) .
For every fixed δ > 0 \delta> 0 δ > 0 , Markov’s inequality gives
Q n , d ⊗ 2 ( B n > δ ) ≤ E Q n , d ⊗ 2 [ B n ] δ ⟶ 0. \mathbb{Q}_{n,d}^{\otimes2}(B_n > \delta) \le\frac{\mathbb{E}_{\mathbb{Q}_{n,d}^{\otimes2}}[B_n]}{\delta} \longrightarrow0. Q n , d ⊗ 2 ( B n > δ ) ≤ δ E Q n , d ⊗ 2 [ B n ] ⟶ 0.
The event { B n > δ } \{B_n > \delta\} { B n > δ } depends only on the two unmarked graphs. Since
Q n , d ⊗ 2 ≈ U n , d ⊗ 2 , \mathbb{Q}_{n,d}^{\otimes2} \approx\mathbb{U}_{n,d}^{\otimes2}, Q n , d ⊗ 2 ≈ U n , d ⊗ 2 ,
contiguity yields
U n , d ⊗ 2 ( B n > δ ) ⟶ 0. \mathbb{U}_{n,d}^{\otimes2}(B_n > \delta) \longrightarrow0. U n , d ⊗ 2 ( B n > δ ) ⟶ 0.
As this holds for every δ > 0 \delta> 0 δ > 0 ,
B n → P 0 , A n → P 1. B_n \xrightarrow{\mathbb{P}} 0,\qquad A_n \xrightarrow{\mathbb{P}} 1. B n P 0 , A n P 1.
For the equivalent sampling formulation, note that 0 ≤ B n ≤ 1 0 \le B_n \le1 0 ≤ B n ≤ 1 . Hence
E U n , d ⊗ 2 [ B n ] ≤ δ + U n , d ⊗ 2 ( B n > δ ) . \mathbb{E}_{\mathbb{U}_{n,d}^{\otimes2}}[B_n] \le\delta+\mathbb{U}_{n,d}^{\otimes2}(B_n>\delta). E U n , d ⊗ 2 [ B n ] ≤ δ + U n , d ⊗ 2 ( B n > δ ) .
Letting first n → ∞ n \to\infty n → ∞ and then δ ↓ 0 \delta\downarrow0 δ ↓ 0 shows that this expectation tends to zero. It is precisely the failure probability obtained by first sampling G 1 , G 2 G_1,G_2 G 1 , G 2 and then selecting one Hamilton cycle uniformly from each graph. □
Note that the theorem permits exceptional pairs of Hamilton cycles, but their proportion tends to zero in probability. It does not claim that every pair is successful, nor does it automatically apply to Hamilton cycles selected according to an arbitrary graph-dependent rule.
Sharpness of the matching scale
Proof of Theorem 5.4. The lower bound is Theorem 5.3. For the upper bound, fix ε > 0 \varepsilon> 0 ε > 0 and set
k = ⌈ ( 1 + ε ) log n log log n ⌉ . k=\left\lceil(1+\varepsilon)\frac{\log n}{\log\log n}\right\rceil. k = ⌈ ( 1 + ε ) log log n log n ⌉ .
Condition on J 1 J_1 J 1 . For any fixed shift s s s , every k k k -subset of ρ s ( J 1 ) \rho_s(J_1) ρ s ( J 1 ) is a matching, and by Theorem C.4 it is contained in J 2 J_2 J 2 with probability p k ( a 2 ) p_k^{(a_2)} p k ( a 2 ) . Therefore
P ( T n ≥ k ∣ J 1 ) ≤ n ( a 1 k ) p k ( a 2 ) ≤ n k ! ( a 1 n 2 a 2 n ) k exp ( O ( k 2 / n ) ) ≤ n 2 − k k ! exp ( O ( k 2 / n ) ) . \begin{aligned}
\mathbb{P}(T_n\ge k\mid J_1)
&\le n\binom{a_1}{k}p_k^{(a_2)}\\
&\le\frac{n}{k!}\left(\frac{a_1}{n}\frac{2a_2}{n}\right)^k\exp(O(k^2/n))\\
&\le\frac{n\,2^{-k}}{k!}\exp(O(k^2/n)).
\end{aligned} P ( T n ≥ k ∣ J 1 ) ≤ n ( k a 1 ) p k ( a 2 ) ≤ k ! n ( n a 1 n 2 a 2 ) k exp ( O ( k 2 / n )) ≤ k ! n 2 − k exp ( O ( k 2 / n )) .
By Stirling’s formula,
log n − k log k + O ( k ) = ( − ε + o ( 1 ) ) log n , \log n-k\log k+O(k)=(-\varepsilon+o(1))\log n, log n − k log k + O ( k ) = ( − ε + o ( 1 )) log n ,
so the last expression tends to zero. Together with Theorem 5.3, this proves the proposition uniformly over the allowed matching sizes.
Proof of Theorem 1.6. For the lower bound, apply Theorem 5.4 to M 1 , 1 M_{1,1} M 1 , 1 and M 2 , 1 M_{2,1} M 2 , 1 .
For the upper bound, condition on R 1 R_1 R 1 , which contains at most q 1 n / 2 q_1n/2 q 1 n /2 distinct edges. Let S S S be a prescribed collection of k k k distinct edges. If S ⊆ R 2 S\subseteq R_2 S ⊆ R 2 , each edge of S S S belongs to at least one of the q 2 q_2 q 2 perfect matchings. There are at most q 2 k q_2^k q 2 k ways of assigning the edges of S S S to these matchings. For a fixed assignment, the probability is zero unless the edges assigned to each matching form a matching. Otherwise, independence and Theorem C.4 give
P ( S ⊆ R 2 ) ≤ q 2 k n − k exp ( O ( k 2 / n ) ) . \mathbb{P}(S\subseteq R_2)\le q_2^k n^{-k}\exp(O(k^2/n)). P ( S ⊆ R 2 ) ≤ q 2 k n − k exp ( O ( k 2 / n )) .
A union bound over shifts and k k k -subsets of ρ s ( R 1 ) \rho_s(R_1) ρ s ( R 1 ) therefore gives
P ( max s ∣ ρ s ( R 1 ) ∩ R 2 ∣ ≥ k ∣ R 1 ) ≤ n ( q 1 q 2 / 2 ) k k ! exp ( O ( k 2 / n ) ) . \mathbb{P}\left(\max_s|\rho_s(R_1)\cap R_2|\ge k\mid R_1\right)\le\frac{n(q_1q_2/2)^k}{k!}\exp(O(k^2/n)). P ( s max ∣ ρ s ( R 1 ) ∩ R 2 ∣ ≥ k ∣ R 1 ) ≤ k ! n ( q 1 q 2 /2 ) k exp ( O ( k 2 / n )) .
For k = ⌈ ( 1 + ε ) log n log log n ⌉ k=\left\lceil(1+\varepsilon)\frac{\log n}{\log\log n}\right\rceil k = ⌈ ( 1 + ε ) l o g l o g n l o g n ⌉ , the right-hand side is n − ε + o ( 1 ) n^{-\varepsilon+o(1)} n − ε + o ( 1 ) . Combined with the lower bound, this proves the theorem.
Technical estimates for the cycle-factor lower bound
This appendix collects the probabilistic and coupling estimates used in Section 6. The deterministic star construction remains in the main text. Throughout, d d d is fixed.
Local sparsity
Lemma D.1 (Local sparsity). Let d ≥ 3 d\ge3 d ≥ 3 be fixed and suppose that
k ≤ 2 a d log n . k\le\frac{2}{a_d}\log n. k ≤ a d 2 log n . Then there exists a constant J = J d J=J_d J = J d such that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , a uniform simple d d d -regular graph G G G on [ n ] [n] [ n ] satisfies
e G ( S ) ≤ ∣ S ∣ + J for every S ⊆ [ n ] with ∣ S ∣ ≤ 2 k . e_G(S)\le|S|+J\qquad\text{for every }S\subseteq[n]\text{ with }|S|\le2k. e G ( S ) ≤ ∣ S ∣ + J for every S ⊆ [ n ] with ∣ S ∣ ≤ 2 k .
Proof. We first work in the d d d -regular configuration model. By assumption, we may take C = 2 / a d C=2/a_d C = 2/ a d , so that k ≤ C log n k\le C\log n k ≤ C log n .
Fix a collection of m = O ( log n ) m=O(\log n) m = O ( log n ) distinct edges. Each edge has two endpoints, and each endpoint has at most d d d half-edges. Hence, there are at most d 2 m d^{2m} d 2 m ways to assign the edge endpoints to configuration half-edges. For any compatible assignment, the probability that the resulting m m m prescribed half-edge pairs occur in a uniform pairing is
∏ j = 0 m − 1 1 d n − ( 2 j + 1 ) ≤ ( 2 d n ) m . \prod_{j=0}^{m-1}\frac{1}{dn-(2j+1)}\le\left(\frac{2}{dn}\right)^m. j = 0 ∏ m − 1 d n − ( 2 j + 1 ) 1 ≤ ( d n 2 ) m .
for all sufficiently large n n n . Hence
P ( all m prescribed ordinary edges occur ) ≤ ( 2 d n ) m . (37) \mathbb{P}(\text{all }m\text{ prescribed ordinary edges occur})\le\left(\frac{2d}{n}\right)^m. \tag*{(37)} P ( all m prescribed ordinary edges occur ) ≤ ( n 2 d ) m . (37)
Fix 1 ≤ v ≤ 2 k 1\le v\le2k 1 ≤ v ≤ 2 k . If a v v v -vertex set spans at least v + J v+J v + J distinct edges, then some prescribed collection of v + J v+J v + J edges is present inside it. By (37) and a union bound, the probability that such a set exists is at most
( n v ) ( ( v 2 ) v + J ) ( 2 d n ) v + J . \binom{n}{v}\binom{\binom{v}{2}}{v+J}\left(\frac{2d}{n}\right)^{v+J}. ( v n ) ( v + J ( 2 v ) ) ( n 2 d ) v + J .
Using ( a b ) ≤ ( e a / b ) b \binom{a}{b}\le(ea/b)^b ( b a ) ≤ ( e a / b ) b and v + J ≥ v v+J\ge v v + J ≥ v , this is bounded by
( e 2 d ) v ( e d v n ) J . (e^2d)^v\left(\frac{edv}{n}\right)^J. ( e 2 d ) v ( n e d v ) J .
Summing over 1 ≤ v ≤ 2 C log n 1\le v\le2C\log n 1 ≤ v ≤ 2 C log n gives at most
2 C log n ( e 2 d ) 2 C log n ( 2 e d C log n n ) J . 2C\log n\,(e^2d)^{2C\log n}\left(\frac{2edC\log n}{n}\right)^J. 2 C log n ( e 2 d ) 2 C l o g n ( n 2 e d C log n ) J .
Choosing the fixed integer J = J d J=J_d J = J d sufficiently large makes this o ( 1 ) o(1) o ( 1 ) . Thus, the local-sparsity event holds with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) in the configuration model. Since the simplicity probability tends to a positive constant, the same high-probability statement holds after conditioning on simplicity.
Lemma D.2 (Pairing concentration). Let r ≥ 1 r\ge1 r ≥ 1 be fixed and let R R R be the configuration-model r r r -regular multigraph on n n n vertices. If U ⊆ [ n ] U\subseteq[n] U ⊆ [ n ] is fixed with u : = ∣ U ∣ ≥ η n u:=|U|\ge\eta n u := ∣ U ∣ ≥ η n , where η > 0 \eta>0 η > 0 is fixed, then for all sufficiently large n n n ,
P ( e R ( U ) < r u 2 4 n ) ≤ exp ( − r η 4 256 n ) . (38) \mathbb{P}\left(e_R(U)<\frac{ru^2}{4n}\right)\le\exp\left(-\frac{r\eta^4}{256}n\right). \tag*{(38)} P ( e R ( U ) < 4 n r u 2 ) ≤ exp ( − 256 r η 4 n ) . (38) Proof. There are L = r n L=rn L = r n half-edges, of which a = r u a=ru a = r u belong to the vertices of U U U . Let X = e R ( U ) X=e_R(U) X = e R ( U ) . Every unordered pair of half-edges in U U U is matched with probability 1 / ( L − 1 ) 1/(L-1) 1/ ( L − 1 ) , and therefore
E X = ( a 2 ) L − 1 = a ( a − 1 ) 2 ( L − 1 ) = r u 2 2 n + O r ( 1 ) . \mathbb{E}X=\frac{\binom{a}{2}}{L-1}=\frac{a(a-1)}{2(L-1)}=\frac{ru^2}{2n}+O_r(1). E X = L − 1 ( 2 a ) = 2 ( L − 1 ) a ( a − 1 ) = 2 n r u 2 + O r ( 1 ) . Expose the uniform pairing one pair at a time, always revealing the half-edge matched to the first unmatched half-edge in a fixed ordering, and let ( Z j ) (Z_j) ( Z j ) be the martingale of the final value of X X X . Two possible partner choices for the exposed half-edge can be coupled by switching at most two pairs. Such a switch changes the number of pairs lying entirely in U U U by at most two, so
∣ Z j − Z j − 1 ∣ ≤ 2. |Z_j-Z_{j-1}|\le2. ∣ Z j − Z j − 1 ∣ ≤ 2. There are L / 2 = r n / 2 L/2=rn/2 L /2 = r n /2 exposure steps. For sufficiently large n n n , using u ≥ η n u\ge\eta n u ≥ η n ,
E X − r u 2 4 n ≥ r η 2 n 8 . (39) \mathbb{E}X-\frac{ru^2}{4n}\ge\frac{r\eta^2n}{8}. \tag*{(39)} E X − 4 n r u 2 ≥ 8 r η 2 n . (39)
The Azuma–Hoeffding inequality (see [14 ] ) therefore gives
P ( X < r u 2 4 n ) ≤ exp ( − ( r η 2 n / 8 ) 2 2 ( L / 2 ) 2 2 2 ) = exp ( − r η 4 256 n ) , \mathbb{P}\left(X < \frac{ru^{2}}{4n}\right) \leq\exp\left(-\frac{(r\eta^{2}n/8)^{2}}{2(L/2)^{2}2^{2}}\right)
= \exp\left(-\frac{r\eta^{4}}{256}n\right), P ( X < 4 n r u 2 ) ≤ exp ( − 2 ( L /2 ) 2 2 2 ( r η 2 n /8 ) 2 ) = exp ( − 256 r η 4 n ) ,
which proves (38) .
Deletion and repair
We now prove the size-reduction coupling used to remove the divisibility condition. The construction is easiest at the pairing level.
Lemma D.3 (Deletion-and-repair coupling). Fix d d d . Let N < n N<n N < n be admissible and set r = n − N = O d ( log n ) r=n-N=O_d(\log n) r = n − N = O d ( log n ) . There is a coupling of a uniform simple d d d -regular graph G G G on [ n ] [n] [ n ] and a uniform simple d d d -regular graph H H H on [ N ] [N] [ N ] such that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
∣ E ( H ) ∖ E ( G [ [ N ] ] ) ∣ ≤ d r 2 . (40) |E(H) \setminus E(G[[N]])| \leq\frac{dr}{2}. \tag*{(40)} ∣ E ( H ) ∖ E ( G [[ N ]]) ∣ ≤ 2 d r . (40)
Proof. First, couple the unconditioned configuration models. Sample a uniform pairing P P P of the d n dn d n half-edges. Delete the d r dr d r half-edges belonging to vertices N + 1 , … , n N+1,\ldots,n N + 1 , … , n , together with all pairs incident to them. Let A A A be the set of surviving half-edges whose matched half-edges were deleted, and write a = ∣ A ∣ a=|A| a = ∣ A ∣ . Then a a a is even and a ≤ d r a\leq dr a ≤ d r . Conditional on the retained partial pairing, pair the elements of A A A uniformly among themselves, and denote the resulting pairing on the d N dN d N surviving half-edges by P ′ P' P ′ .
The distribution of P ′ P' P ′ is invariant under every permutation of the d N dN d N surviving distinguishable half-edges. Indeed, the original pairing is invariant, and the deletion-and-repair operation is equivariant. Since the permutation group acts transitively on perfect matchings of these half-edges, P ′ P' P ′ is a uniform pairing. Every pair of P P P supported entirely on [ N ] [N] [ N ] is retained, and exactly a / 2 ≤ d r / 2 a/2\leq dr/2 a /2 ≤ d r /2 repair pairs are added. Thus (39) holds deterministically at the pairing level.
It remains to pass to simple graphs simultaneously. Let S S S and S ′ S' S ′ be the events that P P P and P ′ P' P ′ are simple. We claim
P ( S △ S ′ ) = o ( 1 ) . (41) \mathbb{P}(S\mathbin{\triangle}S')=o(1). \tag*{(41)} P ( S △ S ′ ) = o ( 1 ) . (41)
A loop or a parallel-edge defect of P P P involving at least one deleted vertex has probability O d ( r / n ) = o ( 1 ) O_d(r/n)=o(1) O d ( r / n ) = o ( 1 ) by the standard first-moment bounds for defects in the configuration model. Every defect supported entirely on [ N ] [N] [ N ] survives unchanged in the retained partial pairing.
New defects can only be created by the repair. Conditional on a a a , symmetry makes A A A a uniform a a a -subset of the surviving half-edges. Hence, the expected number of pairs of half-edges in A A A belonging to the same vertex is
O d ( a 2 N ) = O d ( r 2 n ) = o ( 1 ) . O_d\left(\frac{a^2}{N}\right)=O_d\left(\frac{r^2}{n}\right)=o(1). O d ( N a 2 ) = O d ( n r 2 ) = o ( 1 ) .
With probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , therefore, all half-edges in A A A belong to distinct vertices. Conditionally on this event, the repair creates no loops, and distinct repair edges cannot be parallel.
It remains to exclude parallel edges between the repair pairing and the retained pairing. Condition on A A A and on the repair pairing, but not on the retained pairing. Given A A A , the retained pairing is uniform on the d N − a dN-a d N − a remaining half-edges and is independent of the repair pairing. Fix a repair edge joining distinct vertices u u u and v v v . Since each vertex has at most d d d half-edges in the retained pairing, the conditional probability that this pairing already contains an edge between u u u and v v v is at most
d 2 d N − a − 1 = O d ( N − 1 ) . \frac{d^{2}}{dN-a-1}=O_d(N^{-1}). d N − a − 1 d 2 = O d ( N − 1 ) .
There are a / 2 ≤ d r / 2 a/2\le dr/2 a /2 ≤ d r /2 repair edges, so a union bound gives
P ( a repair edge duplicates a retained edge ) = O d ( r N ) = o ( 1 ) . \mathbb{P}(\text{a repair edge duplicates a retained edge})=O_d\left(\frac{r}{N}\right)=o(1). P ( a repair edge duplicates a retained edge ) = O d ( N r ) = o ( 1 ) .
Consequently, the repair creates no new defects with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Together with the bound on defects involving deleted vertices, this proves (41) .
Both P ( S ) \mathbb{P}(S) P ( S ) and P ( S ′ ) \mathbb{P}(S') P ( S ′ ) tend to the same positive simplicity constant. Since P ( S △ S ′ ) = o ( 1 ) \mathbb{P}(S\mathbin{\triangle}S')=o(1) P ( S △ S ′ ) = o ( 1 ) , conditioning the joint construction on S ∩ S ′ S\cap S' S ∩ S ′ changes either conditional simple marginal by total variation o ( 1 ) o(1) o ( 1 ) . A maximal-coupling correction therefore yields exact marginals G ∼ U n , d G\sim U_{n,d} G ∼ U n , d and H ∼ U N , d H\sim U_{N,d} H ∼ U N , d while preserving (39) outside an event of probability o ( 1 ) o(1) o ( 1 ) .
Proof of Theorem 6.6. Take two independent copies of Theorem D.3. Thus, for i = 1 , 2 i=1,2 i = 1 , 2 , we couple G i ∼ U n , d G_i\sim U_{n,d} G i ∼ U n , d with H i ∼ U N , d H_i\sim U_{N,d} H i ∼ U N , d so that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
∣ E ( H i ) ∖ E ( G i [ [ N ] ] ) ∣ ≤ d r 2 . \lvert E(H_i)\setminus E(G_i[[N]])\rvert\le\frac{dr}{2}. ∣ E ( H i ) ∖ E ( G i [[ N ]])∣ ≤ 2 d r .
The two couplings are independent, so ( G 1 , G 2 ) (G_1,G_2) ( G 1 , G 2 ) and ( H 1 , H 2 ) (H_1,H_2) ( H 1 , H 2 ) have the required product marginals. Let ϕ ∈ S N \phi\in S_N ϕ ∈ S N attain M ( H 1 , H 2 ) M(H_1,H_2) M ( H 1 , H 2 ) and extend it to a permutation of [ n ] [n] [ n ] by mapping the deleted vertices N + 1 , … , n N+1,\ldots,n N + 1 , … , n among themselves. Of the common edges counted by M ( H 1 , H 2 ) M(H_1,H_2) M ( H 1 , H 2 ) , at most d r / 2 dr/2 d r /2 use an edge of H 1 H_1 H 1 absent from G 1 [ [ N ] ] G_1[[N]] G 1 [[ N ]] , and at most d r / 2 dr/2 d r /2 use an edge of H 2 H_2 H 2 absent from G 2 [ [ N ] ] G_2[[N]] G 2 [[ N ]] . Every other common edge remains common under the extended alignment. Hence
M ( G 1 , G 2 ) ≥ M ( H 1 , H 2 ) − d r , M(G_1,G_2)\ge M(H_1,H_2)-dr, M ( G 1 , G 2 ) ≥ M ( H 1 , H 2 ) − d r ,
which is (21) .