January 01, 1970
Resolving a conjecture of Espuny Díaz and Girão [Random Structures Algorithms, 2023], we determine the sharp minimum-degree threshold for Hamiltonicity in graphs perturbed by a uniformly random \(K_r\)-factor. In fact, we prove the stronger pancyclic statement. More generally, for each fixed connected graph \(F\), we study the union of an arbitrary deterministic graph of linear minimum degree and a uniformly random \(F\)-factor. Let \(\alpha^*(F)\) and \(\alpha_{\mathrm{pan}}^*(F)\) denote the corresponding Hamiltonicity and pancyclicity thresholds. We introduce two new parameters, \(\tau_{\operatorname{pc}}(F)\) and \(\tau_{\operatorname{ind}}(F)\), defined by the expected path-cover number and independence number of random induced subgraphs of \(F\), and prove \[\tau_{\operatorname{pc}}(F)\le \alpha^*(F)\le \alpha_{\mathrm{pan}}^*(F)\le \tau_{\operatorname{ind}}(F).\] For \(F=K_r\), the two parameters coincide and are equal to the unique positive solution \(\rho_r\) of \(x^r+rx-1=0\). Hence \(\alpha^*(K_r)=\alpha_{\mathrm{pan}}^*(K_r)=\rho_r\) for every \(r\ge2\).
Hamiltonicity is one of the most fundamental and extensively studied notions in graph theory. A Hamilton cycle in a graph \(G\) is a cycle that contains all vertices of \(G\), and \(G\) is Hamiltonian if it contains a Hamilton cycle. Since deciding whether a graph contains a Hamilton cycle was shown to be NP-complete by Karp [1], it is natural to seek sufficient conditions for the existence of a Hamilton cycle. One of the most classical theorems of this type is the celebrated theorem of Dirac [2], which states that every graph on \(n\ge 3\) vertices with minimum degree at least \(n/2\) contains a Hamilton cycle. While Dirac’s theorem describes the Hamiltonicity of dense graphs, it is also interesting to study the Hamiltonicity of sparse graphs. As a famous example, the binomial random graph \(G(n,p)\) on \(n\) vertices, where each edge is included independently and with probability \(p\), shows that a much lower edge density suffices to guarantee a Hamilton cycle. More precisely, the results of Koršunov [3], and Komlós and Szemerédi [4] show that Hamiltonicity appears around \[p=\frac{\log n+\log\log n}{n}.\]
Motivated by the fruitful studies of Hamiltonicity in both deterministic graphs and random graphs, Bohman, Frieze and Martin [5] introduced the model of randomly perturbed graphs, which combines deterministic and probabilistic viewpoints. They proved that, for every fixed \(\alpha>0\), if \(\delta(H)\ge \alpha n\), then w.h.p. \(H\cup G(n,p)\) is Hamiltonian for \(p\ge C(\alpha)/n\) (we say such an event happens with high probability, or w.h.p. for brevity). Since then, randomly perturbed graphs have been studied extensively. For instance, results are known for bounded-degree spanning trees [6]–[8], general bounded-degree spanning graphs [9], powers of Hamilton cycles [10]–[13], and tilings and \(F\)-factors [14]–[16].
A natural question is whether the binomial random graph can be replaced by other structured random graphs such as random regular graphs. Since for \(d \geq 3\) a uniformly random \(d\)-regular graph is Hamiltonian w.h.p. [17], [18], and this fails for \(d =1, 2\), the relevant cases reduce to a random perfect matching or a random 2-factor. Espuny Díaz and Girão [19] initiated the study of Hamiltonicity of graphs perturbed by a random regular graph, and also considered pancyclicity, that is, the property of containing a cycle of every length \(3,4,\ldots,n\). In particular, they proved that perturbation by a random perfect matching has pancyclicity threshold \(\sqrt2-1\). For the case of random 2-factors, they proved that if \(\delta(G) > n^{3/4+o(1)}\) then w.h.p. \(G \cup G_{n, 2}\) is Hamiltonian. They also showed that this need not hold if \(\delta(G) < \frac{1}{5} \log n\). Draganić and Keevash [20] recently improved this bound by showing that if \(\delta(G) \geq (1+\varepsilon)\sqrt{n \log n /2}\), then w.h.p. \(G \cup G_{n, 2}\) is Hamiltonian, and that the condition on \(\delta(G)\) is tight up to an \(\varepsilon\) factor. In the same paper, they also showed that w.h.p. the union of a fixed \(d\)-regular graph with \(d=\omega(\log^3n)\) and a random 2-factor is Hamiltonian. Building on this, Henderson, Longbrake, Mao, and Morawski [21] subsequently established Hamiltonicity for all \(d\).
In this paper, we study perturbations by \(F\)-factors. Throughout, \(F\) is a fixed connected graph on \(m\ge2\) vertices, and we write \(V(F)=\{1,\ldots,m\}\). A uniformly random \(F\)-factor on an \(n\)-vertex set \(V\), where \(m\mid n\), is generated as follows. Take a uniformly random permutation \(v_1,v_2,\ldots,v_n\) of \(V\). For each \(i=0,1,\ldots,n/m-1\), place a copy of \(F\) on \(\{v_{im+1},v_{im+2},\ldots,v_{im+m}\}\) by identifying \(j\in V(F)\) with \(v_{im+j}\).
In [19], the authors introduced the following definition. For a fixed connected graph \(F\), let \(\alpha^*(F)\) denote the infimum over all \(a\in[0,1]\) such that the following holds: for every \(\varepsilon>0\), every sufficiently large integer \(n\) divisible by \(|V(F)|\), and every \(n\)-vertex graph \(H\) whose minimum degree \(\delta(H)\ge (a+\varepsilon)n\), if \(\mathcal{F}\) is a uniformly random \(F\)-factor on \(V(H)\), then \(H\cup\mathcal{F}\) is w.h.p. Hamiltonian. They showed that \(\alpha^*(K_2)=\sqrt{2}-1\), and conjectured the following:
Conjecture 1. For all \(r \ge 2\), we have that \(\alpha^*(K_r)\) is the unique real positive solution to the equation \(x^r+rx-1=0\).
In this paper, we confirm 1, and more generally, we study the pancyclicity in graphs perturbed by a random \(F\)-factor for an arbitrary fixed connected graph \(F\). For a fixed graph \(F\), we introduce \(\alpha_{\mathrm{pan}}^*(F)\), the pancyclicity analogue of \(\alpha^*(F)\), defined as the infimum over all \(a\in[0,1]\) such that the following holds: for every \(\varepsilon>0\), every sufficiently large integer \(n\) divisible by \(|V(F)|\), and every \(n\)-vertex graph \(H\) whose minimum degree \(\delta(H)\ge (a+\varepsilon)n\), if \(\mathcal{F}\) is a uniformly random \(F\)-factor on \(V(H)\), then w.h.p. \(H\cup\mathcal{F}\) is pancyclic.
Let \(F\) be a fixed connected graph on \(m\ge2\) vertices. For a graph \(G\), let \(\operatorname{ind}(G)\) denote the independence number of \(G\), and let \(\operatorname{pc}(G)\) denote the minimum number of vertex-disjoint paths covering \(V(G)\), where we allow trivial paths and use the convention \(\operatorname{pc}(\emptyset)=0\). Define \[\Phi_F(x) := \sum_{S\subseteq V(F)} \operatorname{ind}(F-S)x^{|S|}(1-x)^{m-|S|}\] and \[\Psi_F(x) := \sum_{S\subseteq V(F)} \operatorname{pc}(F-S)x^{|S|}(1-x)^{m-|S|}.\] If \(F\) is a clique, these two polynomials coincide. In general, by the Gallai–Milgram path-cover bound, \(\Psi_F(x)\le \Phi_F(x)\) for every \(x\in[0,1]\). The lower bound for \(\alpha_{\mathrm{pan}}^*(F)\) comes from \(\Psi_F\): in the extremal complete bipartite construction (see Section 3.1), the part not containing deterministic edges must be covered by paths coming from the random factor. The upper bound comes from \(\Phi_F\): it controls independent sets inside the non-neighborhood of each vertex after the random factor is added. First, we show the following two properties of \(\Phi_F\) and \(\Psi_F\).
Proposition 1. Let \(F\) be a graph on \(m\) vertices. Then the following hold.
\(\Phi_F(x)\) is non-increasing on \([0,1]\).
If \(\Delta_F(x):=mx-\Psi_F(x)\), then \(\Delta_F(x)\) is non-decreasing on \([0,1]\).
Proof. We first record a derivative identity. Let \(h:2^{V(F)}\to\mathbb{R}\), and set \[\Theta_h(x):= \sum_{A\subseteq V(F)} h(A)x^{|A|}(1-x)^{m-|A|}.\] For \(0<x<1\), differentiating term by term gives \[\begin{align} \Theta_h'(x) &= \sum_{A\subseteq V(F)} h(A) \Bigl( |A|x^{|A|-1}(1-x)^{m-|A|} - (m-|A|)x^{|A|}(1-x)^{m-|A|-1} \Bigr) \\ &= \sum_{A\subseteq V(F)} h(A) \Bigl( \sum_{u\in A} x^{|A|-1}(1-x)^{m-|A|} - \sum_{u\in V(F)\setminus A} x^{|A|}(1-x)^{m-|A|-1} \Bigr) \\ &= \sum_{u\in V(F)} \sum_{T\subseteq V(F)\setminus\{u\}} \bigl(h(T\cup\{u\})-h(T)\bigr) x^{|T|}(1-x)^{m-1-|T|}. \end{align}\]
First set \(h(T):=\operatorname{ind}(F-T)\). If \(u\notin T\), then \(F-(T\cup\{u\})\) is an induced subgraph of \(F-T\). Hence \(h(T\cup\{u\})\le h(T)\). Applying the derivative formula to \(\Phi_F\), we have \(\Phi_F'(x)\le 0\) for every \(0<x<1\). Thus \(\Phi_F\) is non-increasing on \((0,1)\). Since \(\Phi_F\) is a polynomial, it is non-increasing on \([0,1]\).
Next set \(h(T):=\operatorname{pc}(F-T)\). Let \(u\notin T\). If \(\mathcal{P}\) is a minimum path cover of \(F-T\), then deleting \(u\) from the path of \(\mathcal{P}\) containing it increases the number of path components by at most one. Hence \(h(T\cup\{u\})\le h(T)+1\). Therefore, \[\Psi_F'(x) \le \sum_{u\in V(F)} \sum_{T\subseteq V(F)\setminus\{u\}} x^{|T|}(1-x)^{m-1-|T|} = m,\] and hence \(\Delta_F'(x)= m-\Psi_F'(x) \ge 0\) for every \(0<x<1\). Thus \(\Delta_F\) is non-decreasing on \((0,1)\). Since \(\Delta_F\) is a polynomial, it is non-increasing on \([0,1]\). ◻
Since \(\Phi_F(0)=\operatorname{ind}(F)\) and \(\Phi_F(1)=0\), by 1(1), \(\Phi_F(x)=mx\) has a unique solution \(\tau_{\operatorname{ind}}(F)\) in \((0,1)\). Moreover, since \(\Delta_F(0)=0-\operatorname{pc}(F)<0\) and \(\Delta_F(1)=m-\operatorname{pc}(\emptyset)=m\), by 1(2), \(\Psi_F(x)=mx\) has a unique solution \(\tau_{\operatorname{pc}}(F)\) in \((0,1)\). Note that \(\tau_{\operatorname{pc}}(F)\le \tau_{\operatorname{ind}}(F)\) since \(\Psi_F(x)\le \Phi_F(x)\) for every \(x\in[0,1]\), and that \(\alpha^*(F)\leq \alpha^*_{\text{pan}}(F)\) since every pancyclic graph contains a Hamilton cycle.
Our main result is the following.
Theorem 1. Let \(F\) be a connected graph on \(m\ge 2\) vertices. Then \[\tau_{\operatorname{pc}}(F)\le\alpha^*(F)\le \alpha_{\mathrm{pan}}^*(F)\le \tau_{\operatorname{ind}}(F).\]
Corollary 1. For every integer \(r\ge 2\), \[\alpha^*(K_r)=\alpha_{\mathrm{pan}}^*(K_r)=\rho_r,\] where \(\rho_r\) is the unique positive solution to the equation \(x^r+rx-1=0\).
Proof. For \(F=K_r\), every non-empty induced subgraph \(F-S\) is a clique. Hence, for every \(S\subsetneq V(F)\), \(\operatorname{ind}(F-S)=\operatorname{pc}(F-S)=1\), while both quantities are \(0\) when \(S=V(F)\). Therefore \(\Phi_{K_r}(x)=\Psi_{K_r}(x)=1-x^r\). Thus \(\tau_{\operatorname{pc}}(K_r)=\tau_{\operatorname{ind}}(K_r)=\rho_r\), where \(\rho_r\) is the positive solution of \(x^r+rx-1=0\). 1 gives \[\rho_r\le\alpha^*(K_r)\le \alpha_{\mathrm{pan}}^*(K_r)\le \rho_r,\] and hence \(\alpha^*(K_r)=\alpha_{\mathrm{pan}}^*(K_r)=\rho_r\). ◻
It is noted that 1 follows immediately from 1.
First, we state the following Chvátal–Erdős type result (Proposition 1 in [22]) which will be used to prove the upper bound.
Theorem 2 ([22]). Let \(G\) be an \(n\)-vertex graph, and let \(k\ge 2\) be an integer. Let \(\kappa(G)\) be the connectivity of \(G\). Suppose that \[\kappa(G)\ge k, \qquad \delta(G)>\frac{n+k^2-k-1}{k+1}, \qquad \delta(G)\ge \alpha(G)+k-2.\] Then \(G\) contains a Hamilton cycle.
Our main probabilistic tool is the following concentration inequality of McDiarmid (see [23]).
Lemma 1 (McDiarmid’s inequality for random permutations). Let \(\pi\) be a uniformly random permutation of an \(n\)-element set, and let \(X=X(\pi)\) be a real-valued function of \(\pi\). Suppose that there is a constant \(c>0\) such that swapping two entries of \(\pi\) changes the value of \(X\) by at most \(c\). Then, for every \(t>0\), \[\Pr\bigl(|X-\mathbb{E} X|\ge t\bigr) \le 2\exp\left(-\frac{2t^2}{c^2 n}\right).\]
We next collect some facts about random \(F\)-factors. First, the following lemma demonstrates the concentration of the sum of independence number or path cover number of each component in a uniformly random \(F\)-factor.
Lemma 2. Let \(F\) be a fixed graph on \(m\) vertices, and let \(h\in\{\operatorname{ind},\operatorname{pc}\}\). For \(x\in[0,1]\), define \[\Theta_h(x) := \sum_{S\subseteq V(F)} h(F-S)x^{|S|}(1-x)^{m-|S|}.\] Let \(n\) be a sufficiently large integer divisible by \(m\), and let \(\mathcal{F}=\{F_1,\dots,F_{n/m}\}\) be a uniformly random \(F\)-factor on an \(n\)-vertex set \(V\). Let \(\mathcal{U}\) be a deterministic family of subsets of \(V\) with \(|\mathcal{U}|\le 2n\). For \(U\subseteq V\), define \[Z_h(U) := \sum_{i=1}^{n/m} h(F_i[U]),\] where \(F_i[U]\) denotes the subgraph of \(F_i\) induced by \(V(F_i)\cap U\). Then, for every fixed \(\xi>0\), with probability at least \(1-\exp(-\Omega_{F,\xi}(n))\), the following holds for every \(U\in\mathcal{U}\): \[\left| Z_h(U)-\frac{n}{m}\Theta_h\left(1-\frac{|U|}{n}\right) \right| \le \xi n.\]
Proof. We first fix \(U\subseteq V\) and compute the expectation of \(Z_h(U)\). Consider one fixed copy of \(F\). For \(S\subseteq V(F)\), the probability that precisely the vertices of \(S\) are mapped to \(V\setminus U\), while the vertices of \(V(F)\setminus S\) are mapped to \(U\), is \[\frac{(n-|U|)_{|S|}(|U|)_{m-|S|}}{(n)_m}.\] Therefore, by linearity of expectation, \[\mathbb{E} Z_h(U) = \frac{n}{m} \sum_{S\subseteq V(F)} h(F-S) \frac{(n-|U|)_{|S|}(|U|)_{m-|S|}}{(n)_m}.\] Since \(m\) is fixed, uniformly in \(U\) and \(S\subseteq V(F)\) we have \[\frac{(n-|U|)_{|S|}(|U|)_{m-|S|}}{(n)_m} = \left(1-\frac{|U|}{n}\right)^{|S|}\left(\frac{|U|}{n}\right)^{m-|S|} + O\left(\frac{1}{n}\right).\] Hence \[\label{expe} \mathbb{E} Z_h(U) = \frac{n}{m}\Theta_h\left(1-\frac{|U|}{n}\right)+O(1).\tag{1}\]
View \(Z_h(U)\) as a function of the random permutation \(v_1,\dots,v_n\) used to generate the \(F\)-factor. If two entries of the permutation are swapped, at most two copies of \(F\) are affected. Moreover, for every induced subgraph \(J\) of \(F\), we have \(0\le h(J)\le m\). Thus swapping two entries changes \(Z_h(U)\) by at most \(2m\). Therefore, by McDiarmid’s inequality for random permutations, we obtain \[\Pr\left( \left|Z_h(U)-\mathbb{E} Z_h(U)\right|>\frac{\xi n}{2} \right) \le 2\exp\left(-\frac{\xi^2}{8m^2}n\right).\]
By taking union bound over all \(U\in \mathcal{U}\), we have \[\Pr\left( \exists\, U\in\mathcal{U}: \left|Z_h(U)-\mathbb{E} Z_h(U)\right|>\frac{\xi n}{2} \right) \le 4n\exp\left(-\frac{\xi^2}{8m^2}n\right) \le \exp(-\Omega_{F,\xi}(n)).\] Hence, with probability at least \(1-\exp(-\Omega_{F,\xi}(n))\), we have \(\left|Z_h(U)-\mathbb{E} Z_h(U)\right| \le \xi n/2\) for every \(U\in\mathcal{U}\). Combining this with 1 , we obtain, for all \(U\in\mathcal{U}\), \[\left| Z_h(U) - \frac{n}{m}\Theta_h\left(1-\frac{|U|}{n}\right) \right| \le \xi n.\] This completes the proof. ◻
The next lemma proves that a uniformly random \(F\)-factor joins any two linear-sized disjoint sets with exponentially high probability.
Lemma 3. Let \(0<c<1\), and let \(n\) be a sufficiently large integer divisible by \(m\). Let \(V\) be an \(n\)-vertex set, and let \(X,Y\subseteq V\) be disjoint subsets with \(|X|,|Y|\ge cn\). Let \(\mathcal{F}\) be a uniformly random \(F\)-factor on \(V\), where \(F\) is a non-empty graph on \(m\) vertices. Then, \[\Pr\bigl(E_{\mathcal{F}}(X,Y)=\emptyset\bigr) \le \exp(-\Omega_{F,c}(n)).\] Here \(E_{\mathcal{F}}(X,Y)\) denotes the set of edges of \(\mathcal{F}\) with one endpoint in \(X\) and the other endpoint in \(Y\).
Proof. Since \(F\) is non-empty, we may fix an edge \(ab\in E(F)\). Let \(M\) be the number of copies of \(F\) in \(\mathcal{F}\) for which the vertex corresponding to \(a\) lies in \(X\) and the vertex corresponding to \(b\) lies in \(Y\). For each copy, the ordered pair of vertices corresponding to \(a\) and \(b\) is uniformly distributed over all ordered pairs of distinct vertices of \(V\). Hence \[\mathbb{E} M = \frac{n}{m}\cdot \frac{|X||Y|}{n(n-1)}=\Omega_{F,c}(n).\]
Note that swapping two entries of the permutation changes \(M\) by at most \(2\). Since \(|X|,|Y|\geq cn\), McDiarmid’s inequality gives that for random permutations, \[\Pr\left(|M-\mathbb{E} M|\ge \mathbb{E} M\right) \le \exp(-\Omega_{F,c}(n)).\] Therefore \[\Pr\bigl(E_{\mathcal{F}}(X,Y)=\emptyset\bigr) \le \Pr(M=0) \le \Pr\left(|M-\mathbb{E} M|\ge \mathbb{E} M\right) \le \exp(-\Omega_{F,c}(n)).\] This proves the lemma. ◻
The lower bound follows from the same construction in [24], which we include for completeness. Indeed, it suffices to show that for every \(0\le x<\tau_{\operatorname{pc}}(F)\), there exists a graph \(H\) with minimum degree \(xn\) such that w.h.p. \(H\cup\mathcal{F}\) is not pancyclic, where \(\mathcal{F}\) is a uniformly random \(F\)-factor.
Fix such an \(x\). Since for every \(S\subseteq V(F)\), \(\operatorname{pc}(F-S)\leq |V(F-S)|=m-|S|\), we have that \[\Psi_F(x) \le \sum_{S\subseteq V(F)} (m-|S|)x^{|S|}(1-x)^{m-|S|} = m(1-x).\] Thus, the inequality \(\Psi_F(x)>mx\) implies \(x<1/2\).
Let \(V=A\cup B\), where \(|A|=\lfloor xn\rfloor\) and \(|B|=n-|A|\), and let \(H:=K_{A,B}\). Then \(\delta(H)=|A|=\lfloor xn\rfloor\) since \(|A|<|B|\).
Consider the subgraph \(\mathcal{F}[B]\). Since different copies of \(F\) are vertex-disjoint, \[\operatorname{pc}(\mathcal{F}[B]) = \sum_{F_i\in\mathcal{F}}\operatorname{pc}(F_i[B]).\] By 2, applied with \(h=\operatorname{pc}\) and \(U=B\), we have w.h.p. \[\operatorname{pc}(\mathcal{F}[B]) = \left(\frac{\Psi_F(x)}{m}+o(1)\right)n.\] Since \(\Psi_F(x)>mx\), it follows that w.h.p. \(\operatorname{pc}(\mathcal{F}[B])>|A|\).
We now show that this prevents the existence of a Hamilton cycle in \(H\cup\mathcal{F}\). Suppose, for a contradiction, that \(H\cup\mathcal{F}\) contains a Hamilton cycle \(C\). The graph \(H\) has no edges inside \(B\), so all edges of \(C[B]\) lie in \(\mathcal{F}[B]\). After deleting the vertices of \(A\) from \(C\), the remaining vertices of \(B\) are covered by at most \(|A|\) vertex-disjoint paths. These paths use only edges of \(\mathcal{F}[B]\). Therefore \(\operatorname{pc}(\mathcal{F}[B])\le |A|\), contradicting the inequality above. Thus w.h.p. \(H\cup\mathcal{F}\) contains no Hamilton cycle. Hence \(\alpha^*(F)\ge \tau_{\operatorname{pc}}(F)\). 0◻
First, we prove that w.h.p. the graph \(H\cup \mathcal{F}\) contains every short cycle.
Lemma 4. Let \(F\) be a fixed connected graph on \(m\ge2\) vertices, and let \(0<a<1\). For every sufficiently large integer \(n\) divisible by \(m\) and every \(n\)-vertex graph \(H\) with \(\delta(H)\ge an\), w.h.p. the graph \(H\cup\mathcal{F}\), where \(\mathcal{F}\) is a uniformly random \(F\)-factor on \(V(H)\), contains a cycle of every length \(3\le \ell\le an/2\).
Proof. Fix an edge \(\{p,q\}\in E(F)\) and orient it as \(pq\). For an integer \(s\) with \(2\le s\le an/2-1\), let \(P_s\) be the set of ordered pairs \((x,y)\in V(H)^2\) for which \(H\) contains an \(x\)-\(y\) path of length exactly \(s\). We first show that \(|P_s|\ge an^2/2\) for sufficiently large integer \(n\).
Fix \(x\in V(H)\). Since \(\delta(H)\ge an>s-1\), we can greedily extend a path from \(x\) and thus have a path \(x=x_0,x_1,\ldots,x_{s-1}\) of length \(s-1\). For every \(y\in N_H(x_{s-1})\setminus\{x_0,\ldots,x_{s-2}\}\), the sequence \(x_0,x_1,\ldots,x_{s-1},y\) is a simple path of length \(s\). There are at least \(an-(s-1)\ge an/2\) choices for \(y\). Summing over \(x\), we get \(|P_s|\ge an^2/2\).
Let \(M_s\) be the number of copies of \(F\) in \(\mathcal{F}\) for which the vertex corresponding to \(p\) and the vertex corresponding to \(q\) form an ordered pair in \(P_s\). For each copy, by symmetry of the uniform distribution over all \(F\)-factors, this ordered pair is uniformly distributed over all ordered pairs of distinct vertices of \(V(H)\). Hence \[\mathbb{E} M_s \ge \frac{n}{m}\cdot \frac{an^2/2}{n(n-1)} =\Omega_{F,a}(n).\] Swapping two entries of the random permutation used to generate \(\mathcal{F}\) changes \(M_s\) by at most \(2\). Thus the McDiarmid’s inequality gives \[\Pr(M_s=0)\le \Pr\left(|M-\mathbb{E} M|\ge \mathbb{E} M\right)\le \exp(-\Omega_{F,a}(n)).\] Taking a union bound over all \(s\le an/2-1\), w.h.p. \(M_s>0\) for every such \(s\). If \(M_s>0\), then some random-factor edge \(xy\) has endpoints joined in \(H\) by a path of length \(s\), and this path together with \(xy\) gives a cycle of length \(s+1\). Therefore all cycle lengths \(3\le \ell\le an/2\) occur w.h.p. ◻
Next, we prove that w.h.p. the graph \(H\cup \mathcal{F}\) also contains every long cycle.
Lemma 5. Let \(F\) be a fixed connected graph on \(m\ge2\) vertices, and let \(a>\tau_{\operatorname{ind}}(F)\). Then there is a constant \(c=c(F,a)>0\) such that the following holds for every sufficiently large integer \(N\). Let \(G\) be an \(N\)-vertex graph with \(\delta(G)\ge aN\), and let \(B\subseteq V(G)\) with \(|B|<m\) and \(m\mid N-|B|\). If \(\mathcal{F}'\) is a uniformly random \(F\)-factor on \(V(G)\setminus B\), then \[\Pr\bigl(G\cup\mathcal{F}'\text{ is Hamiltonian}\bigr) \ge 1-\exp(-cN).\]
Proof. Put \(N':=N-|B|\) and \(V':=V(G)\setminus B\). Choose \(b\) with \(\tau_{\operatorname{ind}}(F)<b<a\). Since \(\Phi_F(b)<bm<am\) by 1, choose \(\eta>0\) such that \(\Phi_F(b)/m\le a-3\eta\).
For each \(v\in V(G)\), set \(C_v:=V(G)\setminus N_G(v)\) and set \(C'_v:=C_v\cap V'\). Since \(\delta(G)\ge aN\), for sufficiently large integer \(N\), we have \(1-\frac{|C'_v|}{N'}\ge b\). Let \[Z_v:=\sum_{F_i\in\mathcal{F}'}\operatorname{ind}(F_i[C'_v]).\] By the proof of 2, with \(h=\operatorname{ind}\) and the family \(\{C'_v:v\in V(G)\}\), we have that with probability at least \(1-\exp(-\Omega_{F,a}(N))\), for every \(v\in V(G)\), \[Z_v \le \frac{N'}{m}\Phi_F\left(1-\frac{|C'_v|}{N'}\right)+\eta N' \le \frac{N'}{m}\Phi_F(b)+\eta N' \le (a-2\eta)N.\] Here we used that \(\Phi_F\) is non-increasing.
On this event, every independent set \(I\) of \(J:=G\cup\mathcal{F}'\) has size at most \((a-\eta)N\). Indeed, choose \(v\in I\). Since \(I\) is independent in \(G\), we have \(I\subseteq C_v\). Moreover, \(I\cap V'\) is independent in \(\mathcal{F}'[C'_v]\), so \(|I|\le Z_v+|B|\le (a-\eta)N\) for sufficiently large integer \(N\). Thus \(\operatorname{ind}(J)\le (a-\eta)N\).
It remains to verify the connectivity condition in 2. Choose an integer \(k\ge2\) such that \(a>1/(k+1)\). Fix \(W\subseteq V(G)\) with \(|W|\le k-1\), and let \(C\) be a component of \(G-W\). For any \(u\in C\), all neighbors of \(u\) in \(G\) lie in \(C\cup W\), and hence \(|C|\ge aN-|W|+1\ge aN-k+2\). Consequently, each component \(C\) of \(G-W\) satisfies \(|C\cap V'|\ge (a/2)N\) for sufficiently large integer \(N\), and hence there are only \(O_{a,k}(1)\) such components.
For any two distinct components \(C,D\) of \(G-W\), 3 applied inside \(V'\) gives \[\Pr\bigl(E_{\mathcal{F}'}(C\cap V',D\cap V')=\emptyset\bigr) \le \exp(-\Omega_{F,a}(N)).\] A union bound over all \(O(N^{k-1})\) choices of \(W\) and all component pairs shows that, with probability at least \(1-\exp(-\Omega_{F,a,k}(N))\), \(J-W\) is connected for every \(|W|\le k-1\). Hence \(\kappa(J)\ge k\).
Lastly, for sufficiently large integer \(N\), we have \[\delta(J)\ge aN> \frac{N+k^2-k-1}{k+1}\] and, using \(\operatorname{ind}(J)\le(a-2\eta)N\), we get \(\delta(J)\ge aN\ge \operatorname{ind}(J)+k-2\). Together with \(\kappa(J)\ge k\), 2 implies that \(J\) is Hamiltonian. This proves the lemma. ◻
Lemma 6. Let \(F\) be a fixed connected graph on \(m\ge2\) vertices, and let \(a>\tau_{\operatorname{ind}}(F)\). Then there is a constant \(C=C(F,a)>0\) such that the following holds. For every sufficiently large integer \(n\) divisible by \(m\), every \(n\)-vertex graph \(H\) with \(\delta(H)\ge an\), w.h.p. the graph \(H\cup\mathcal{F}\), where \(\mathcal{F}\) is a uniformly random \(F\)-factor on \(V(H)\), contains a cycle of every length \(C\log n\le \ell\le n\).
Proof. Generate \(\mathcal{F}\) from a uniformly random permutation \(v_1,\ldots,v_n\). For each \(\ell\), let \(X_\ell:=\{v_1,\ldots,v_\ell\}\). Choose \(b\) with \(\tau_{\operatorname{ind}}(F)<b<a\). By the hypergeometric Chernoff’s bound, for every fixed \(v\in V(H)\) and \(\ell\), we have \(\Pr\bigl(|N_H(v)\cap X_\ell|<b\ell\bigr) \le \exp(-\Omega_{a,b}(\ell))\). Choosing \(C\) sufficiently large and taking a union bound over all \(v\in V(H)\) and all \(\ell\ge C\log n\), we obtain w.h.p. \(\delta(H[X_\ell])\ge b\ell\) for every \(\ell\ge C\log n\).
Fix such an \(\ell\), and write \(\ell=qm+r\), where \(0\le r<m\). Let \(B_\ell:=\{v_{qm+1},\ldots,v_{qm+r}\}\) and \(X'_\ell:=X_\ell\setminus B_\ell\). Conditioned on \(X_\ell\) and \(B_\ell\), the first \(q\) complete blocks of the permutation form a uniformly random \(F\)-factor on \(X'_\ell\). Applying 5 to the graph \(H[X_\ell]\), with the exceptional set \(B_\ell\) and parameter \(b\), shows that \(H[X_\ell]\cup\mathcal{F}[X_\ell]\) contains a Hamilton cycle with probability at least \(1-\exp(-\Omega_{F,a}(\ell))\). A union bound over all \(\ell\ge C\log n\) completes the proof. ◻
Fix \(a>\tau_{\operatorname{ind}}(F)\). Let \(H\) be an \(n\)-vertex graph with \(\delta(H)\ge an\), where \(n\) is a sufficiently large integer divisible by \(m\), and let \(\mathcal{F}\) be a uniformly random \(F\)-factor on \(V(H)\).
By 4, w.h.p. \(H\cup\mathcal{F}\) contains cycles of all lengths \(3\le \ell\le an/2\). By 6, w.h.p. \(H\cup\mathcal{F}\) contains cycles of all lengths \(C\log n\le \ell\le n\) for some constant \(C=C(F,a)\). Since \(C\log n\le an/2\) for sufficiently large integer \(n\), these two ranges cover every \(\ell\in\{3,4,\ldots,n\}\). Hence w.h.p. \(H\cup\mathcal{F}\) is pancyclic.
Since \(a>\tau_{\operatorname{ind}}(F)\) was arbitrary, the definition of \(\alpha_{\mathrm{pan}}^*(F)\) gives \(\alpha_{\mathrm{pan}}^*(F)\le \tau_{\operatorname{ind}}(F)\). This completes the proof of 1. 0◻
1 determines the exact threshold for clique factors. However, for non-complete connected \(F\), the interval in 1 is genuinely non-degenerate.
Proposition 2. Let \(F\) be connected. Then \(\tau_{\operatorname{pc}}(F)=\tau_{\operatorname{ind}}(F)\) if and only if \(F\) is a complete graph. In particular, if \(F\) is connected and not complete, then \(\tau_{\operatorname{pc}}(F)<\tau_{\operatorname{ind}}(F)\).
Proof. The complete graph case follows from the proof of 1. Conversely, suppose that \(F\) is connected and not complete. Then \(F\) contains an induced copy of \(P_3\): take a shortest path between two non-adjacent vertices and use its first three vertices. Hence for some \(S\subseteq V(F)\) we have \(F-S\cong P_3\), and for this induced subgraph \(\operatorname{ind}(F-S)=2>1=\operatorname{pc}(F-S)\). Since all coefficients in \(\Phi_F(x)-\Psi_F(x)\) are non-negative, this implies \(\Phi_F(x)>\Psi_F(x)\) for every \(0<x<1\). At \(t=\tau_{\operatorname{pc}}(F)\) we therefore have \(mt=\Psi_F(t)<\Phi_F(t)\), so \(mt-\Phi_F(t)<0\). As \(x\mapsto mx-\Phi_F(x)\) is strictly increasing and has its unique zero at \(\tau_{\operatorname{ind}}(F)\), it follows that \(t<\tau_{\operatorname{ind}}(F)\). ◻
2 shows that our two general parameters coincide only for clique factors. It would thus be interesting to determine the exact thresholds for non-clique factors.
Question 1. Determine \(\alpha^*(F)\) and \(\alpha_{\mathrm{pan}}^*(F)\) for connected non-complete graphs \(F\), even for \(F=P_3\).
Department of Mathematics, University of California, Irvine. Partially supported by National Key Research and Development Program of China under grant 2023YFA1010203. Email: dingjiam@uci.edu``.↩︎
School of Mathematics and Statistics, Xi’an Jiaotong University. Partially supported by National Key Research and Development Program of China under grant 2023YFA1010203. Email: fhyuan1@gmail.com.↩︎
School of Mathematics, Shandong University, Jinan, China. Supported by National Natural Science Foundation of China (No. 12401457), China Postdoctoral Science Foundation (No. 2024M761780), the Natural Science Foundation of Shandong Province
(No. ZR2024QA067) and the Young Talent of Lifting engineering for Science and Technology in Shandong, China (No. SDAST2025QTA074). Email: gracezhou@sdu.edu.cn.↩︎