Proof of Theorem 1.2. By Lemma 3.5, it suffices to show that for any loose Hamilton cycle $H$ in $G$ and loose path $P_0\subset H$ of length $t$ , there are at least $\gamma n^{m-1}$ feasible $(P_0,H)$ -switchings of size $m$ . Lemma 3.10 then implies that it is sufficient to find $\gamma n^{m-1}$ $t$ -balanced $m$ -splittings $\mathcal P$ of $H$ with $P_0\in {\mathcal P}$ and such that $\mathcal P$ is suitable for $P_0$ and admits a viable partition. The existence of these splittings is then given by Lemma 3.11.

Proof of 3.5. Let $H_*$ be a loose Hamilton cycle of $G$ chosen uniformly at random. Recall the hierarchy of the parameters: $1/n\ll \mu \ll \gamma \ll 1/m\ll 1/t$ in (3.1).

For every $P_0$ loose path of length $t$ in $G$ and every $e_0,f_0\in E(P_0)$ with $|e_0\cap f_0|\leq 1$ and $\chi (e)=\chi (f)$ define the events $A(e_0,f_0;P_0)=\{P_0\subset H_*\}$ . Similarly, for every pair of vertex-disjoint loose paths $P_0,Q_0$ of length $t$ in $G$ and every $e_0\in E(P_0)$ and $f_0\in E(Q_0)$ with $\chi (e)=\chi (f)$ , define $B(e_0,f_0;P_0,Q_0)=\{P_0,Q_0\subseteq H_*\}$ . Then we define

\begin{equation*} \begin{aligned} \mathcal{A}&=\{A(e_0,f_0 \, ; \, P_0) \, : \, \mathbb{P}[A(e_0,f_0 \, ; \, P_0)]\gt 0\},\\ \mathcal{B}&={\{B(e_0,f_0 \, ; \, P_0,Q_0) \, : \, \mathbb{P}[B(e_0,f_0 \, ; \, P_0,Q_0)]\gt 0\}},\\ \mathcal{E}&= \mathcal{A} \cup \mathcal{B}. \end{aligned} \end{equation*}

Note that if none of the events in $\mathcal{E}$ hold, then $H_*$ is rainbow. Indeed, for every pair $e_0,f_0\in E(H_*)$ we have $|e_0\cap f_0|\leq 1$ and by avoiding the events in $\mathcal{E}$ , any such pair satisfies $\chi (e)\neq \chi (f)$ .

For each $A=A(e_0,f_0;P_0)\in \mathcal{A}$ , we write $V(A)\,:\!=\,V(P_0)$ and for each $B=B(e_0,f_0;P_0,Q_0)$ , we write $V(B)\,:\!=\,V(P_0)\cup V(Q_0)$ . Consider the graph $\Gamma$ with $V(\Gamma )=\mathcal{E}$ where for every $E_1,E_2\in \mathcal{E}$ we have $E_1E_2\in E(\Gamma )$ if and only if $V(E_1)\cap V(E_2)\neq \emptyset$ . We will choose values $p_{\mathcal{A}},p_{\mathcal{B}}\in [0,1/2)$ such that $\Gamma$ is a $\textbf {p}$ -dependency graph for $\mathcal{E}$ , where $p_A=p_{\mathcal{A}}$ for all $A\in \mathcal{A}$ and $p_B=p_{\mathcal{B}}$ for all $B\in \mathcal{B}$ . For ${\mathcal X}\in \{\mathcal{A},\mathcal{B}\}$ , define

\begin{equation*} d_{{\mathcal X}} =\max _{E\in \mathcal{E}} |\{X\in {\mathcal X} \, : \, EX\in E(\Gamma )\}|. \end{equation*}

To apply Corollary 2.4, it suffices to check that $p_{\mathcal{A}}d_{\mathcal{A}}+p_{\mathcal{B}}d_{\mathcal{B}} \leq 1/4$ .

To bound the degrees in $\Gamma$ , we bound the number of events whose vertex set intersects a given vertex $v\in V(G)$ . Recall that $T=t(k-1)+1$ is the number of vertices of a loose path of length $t$ .

For every $v\in V(G)$ , we claim that

(4.1) \begin{equation} |A\in \mathcal{A} \, : \, v\in V(A)|\leq 2(k+1) T!\mu n^{T-1}. \end{equation}

Indeed, suppose that $A=A(e_0,f_0;P_0)\in \mathcal{A}$ with $v\in V(A)$ . There are at most $(k+1)\mu n^{2k-1}$ pairs of edges $e_0,f_0\in E(H_*)$ of the same colour with $|e_0\cap f_0|\leq 1$ ; indeed, there are at most $n^{k}$ choices for $e_0$ , at most $(k+1)$ for $e_0\cap f_0$ and at most $\mu n^{k-1}$ for $f_0$ , by (B). From them, at most $(k+1)\mu n^{2k-2}$ pairs satisfy $v\in e_0\cup f_0$ (as one can assume that $v\in e_0$ which gives at most $n^{k-1}$ choices for $e_0$ ). If $v\notin (e_0\cup f_0)$ , then there are at most $T!n^{T-2k}$ ways to complete the path $P_0$ containing both edges, and if $v\in (e_0\cup f_0)$ there are at most $T!n^{T-2k+1}$ ways to do it. In total, $v$ intersects with at most $2(k+1)T!\mu n^{T-1}$ events in $\mathcal{A}$ , proving (4.1).

For every $v\in V(G)$ , we claim that

(4.2) \begin{equation} |B\in \mathcal{B} \, : \, v\in V(B)|\leq 2 (T!)^2 \mu n^{2T-2}. \end{equation}

Indeed, suppose that $B=B(e_0,f_0;P_0,Q_0)\in \mathcal{B}$ with $v\in V(B)$ . If $v\in (e_0\cup f_0)$ , we may assume that $v\in e_0$ and there are at most $n^{k-1}$ choices for $e_0$ and at most $\mu n^{k-1}$ for $f_0$ of the same colour, again by (B). Then there are at most $(T!)^2 n^{2T-2k}$ choices for $P_0$ and $Q_0$ containing $e_0$ and $f_0$ respectively. If $v\notin (e_0\cup f_0)$ , then there are at most $\mu n^{2k-1}$ pairs $e_0,f_0$ of the same colour, and at most $(T!)^2 n^{2T-2k-1}$ choices for $P_0$ and $Q_0$ containing $e_0$ and $f_0$ respectively, such that $v\in P_0\cup Q_0$ . In total, $v$ intersects at most $2 (T!)^2 \mu n^{2T-2}$ events in $\mathcal{B}$ , proving (4.2).

By the definition of $\Gamma$ and since $|V(E)|\leq 2T$ for all $E\in \mathcal{E}$ , there exists $C=C(k,t)$ such that

(4.3) \begin{align} d_{\mathcal{A}} \lt C \mu n^{T-1} \quad \text{ and } \quad d_{\mathcal{B}} \lt C \mu n^{2T-2}. \end{align}

In order to bound $p_{\mathcal{A}}$ and $p_{\mathcal{B}}$ we will use switchings. Recall that $p_{\mathcal{A}}$ is an upper bound on $\mathbb{P}[A\mid \cap _{E \in {\mathcal{E}'}} \overline {E}]$ where $A \in \mathcal{A}$ and

(4.4) \begin{equation} {\mathcal{E}'} \subseteq \{E\in \mathcal{E}\setminus \{A\} \,:\, AE \notin E(\Gamma )\}. \end{equation}

Fix $A=A(e_0,f_0 \, ; \, P_0)\in \mathcal{A}$ and $\mathcal{E}'$ as in (4.4). Let ${\mathcal H}={\mathcal H}(\mathcal{E}')$ be the collection of loose Hamilton cycles of $G$ that satisfy $\cap _{E \in {\mathcal{E}'}} \overline {E}$ , which we may assume is non-empty. Let ${\mathcal H}_0 = \{H \in {\mathcal H} \, : \, P_0 \subset H\}$ . Consider the bipartite multigraph ${\mathcal F}_A$ with parts ${\mathcal H}_0$ and $\mathcal H$ and where an edge is added between $H \in {\mathcal H}_0$ and $H'\in {\mathcal H}$ for each feasible $(P_0,H)$ -switching $Y=({\mathcal P},H',{\mathcal P}')$ of size $m$ .

In fact, for every feasible $(P_0,H)$ -switching $Y=({\mathcal P},H',{\mathcal P}')$ , we have $H'\in {\mathcal H}\setminus {\mathcal H}_0$ . Indeed, by Definition 3.3, since $V(P_0)$ is transverse with respect to ${\mathcal P}'$ , $P_0$ is not in $H'$ . Moreover, by Definition 3.4, all edges in $H'$ that are not in $H$ either intersect $P_0$ or have a unique colour in $H'$ . However, by the definition of $\Gamma$ and (4.4), all events that intersect $P_0$ are not in $\mathcal{E}'$ , thus $H'\in {\mathcal H}$ .

Let $\delta _A$ be the minimum degree in ${\mathcal F}_A$ of the vertices in ${\mathcal H}_0$ and $\Delta _A$ be the maximum degree in ${\mathcal F}_A$ of the vertices in $\mathcal H$ . Double-counting the edges of ${\mathcal F}_A$ , we obtain

(4.5) \begin{equation} \mathbb{P}[A \mid \cap _{E \in {\mathcal{E}'}} {\overline {E}} ] = \frac {|{\mathcal H}_0|}{|{\mathcal H}|} \le \frac {\Delta _A}{\delta _A}. \end{equation}

It suffices to upper bound $\Delta _A$ and lower bound $\delta _A$ . The hypothesis of the lemma and the fact that every feasible switching produces a loose Hamilton cycle in $\mathcal H$ , imply that $\delta _A \ge \gamma n^{m-1}$ . To bound $\Delta _A$ , we fix any $H'\in {\mathcal H}$ and bound the number of pairs $(H,Y)$ where $H \in {\mathcal H}_0$ and $Y=({\mathcal P},H',{\mathcal P}')$ is a feasible $(P_0,H)$ -switching of size $m$ . By the previous observation, it suffices to check it for $H'\in {\mathcal H}\setminus {\mathcal H}_0$ . By condition (II) in Definition 3.3 , all vertices in $V(P_0)$ are in different parts of ${\mathcal P}'$ . We first construct ${\mathcal P}'$ . As $P_0$ is fixed by $A$ , the number of ways to choose $T$ paths in $H'$ of length at most $2t$ and each one containing exactly one vertex in $V(P_0)$ is a constant only depending on $t,k$ . Additionally, there are at most $n^{m-T}$ choices to complete ${\mathcal P}'$ with $m-T$ paths in $H'$ (each factor of $n$ corresponding to a choice of starting point in $H'$ for one of the remaining paths in ${\mathcal P}'$ ). Once ${\mathcal P}'$ has been fixed, the number of ways to construct $\mathcal P$ and $H$ is a constant only depending on $t,k,m$ . So $\Delta _A \le C' n^{m-T}$ , for $C'=C'(k,t,m)$ . We obtain

(4.6) \begin{align} \mathbb{P}[A \vert \cap _{E \in {\mathcal{E}'}} {\overline {E}} ] \leq C' \gamma ^{-1} n^{1-T} =\!: \, p_{\mathcal{A}} \; . \end{align}

Similarly, we choose $p_{\mathcal{B}}$ to be an upper bound on $\mathbb{P}[B\mid \cap _{E \in {\mathcal{E}'}} \overline {E}]$ where $B=B(e_0,f_0;P_0,Q_0) \in \mathcal{B}$ and $\mathcal{E}'$ satisfying (4.4) where $A$ is replaced by $B$ . Define ${\mathcal H}={\mathcal H}(\mathcal{E}')$ as before and now let ${\mathcal H}_{0} = \{H \in {\mathcal H} \, : \, P_0,Q_0 \subset H\}$ and construct the bipartite multigraph ${\mathcal F}_B$ with parts ${\mathcal H}_{0}$ and $\mathcal H$ , where an edge is added between $H \in {\mathcal H}_{0}$ and $H'\in {\mathcal H}$ for each pair $(Y,Z)$ where

1. – $Y=({\mathcal P},H_Y,{\mathcal P}_Y)$ is a feasible $(P_0,H)$ -switching of size $m$ , such that $V({\mathcal P})\cap V(Q_0)=\emptyset$ , and

2. – $Z=({\mathcal Q},H',{\mathcal Q}')$ is a feasible $(Q_0,H_Y)$ -switching of size $m$ , such that $V({\mathcal Q})\cap V(P_0)=\emptyset$ .

As in the previous observation, if there is an edge between $H$ and $H'$ , then $H'\in {\mathcal H}\setminus {\mathcal H}_{0}$ . Define $\Delta _B$ and $\delta _B$ analogously to $\Delta _A$ and $\delta _A$ for the multigraph ${\mathcal F}_B$ . To compute $\delta _B$ , note that some switchings are invalid as they violate the disjointness conditions. However, given $P_0$ and $Q_0$ , there is some constant $\tilde {C}\gt 0$ depending only on $t$ and $k$ such that there are at most $\tilde {C}n^{m-2}$ many $(P_0,H)$ -switchings $Y=({\mathcal P},H_Y,{\mathcal P}_Y)$ such that $V({\mathcal P})\cap V(Q_0)\neq \emptyset$ and at most $\tilde {C}n^{m-2}$ many $(Q_0,H_Y)$ -switchings $Z=({\mathcal Q},H',{\mathcal Q}')$ such that $V({\mathcal Q})\cap V(P_0)\neq \emptyset$ . Therefore a negligible proportion of the the pairs of switchings are disallowed and by the hypothesis of the lemma, $\delta _B\geq \tfrac {1}{2}\gamma ^2 n^{2m-2}$ . Similarly as before, we have that $\Delta _B \le C'n^{2(m-T)}$ . It follows that

(4.7) \begin{align} \mathbb{P}[B \vert \cap _{E \in {\mathcal{E}'}} {\overline {E}} ] \leq 2C' \gamma ^{-2} n^{2-2T} \,=\!:\, p_{\mathcal{B}} \;. \end{align}

Combining equation (4.3), (4.6) and (4.7), and since $\mu \ll \gamma , 1/m, 1/t, 1/k$ , we have that $p_{\mathcal{A}}d_{\mathcal{A}}+p_{\mathcal{B}}d_{\mathcal{B}} \leq 1/4$ . The lemma now follows by applying Corollary 2.4.

Proof of Lemma 3.10. We fix some path $P_0$ of length $t$ in $G$ , some loose Hamilton cycle $H$ containing $P_0$ and some $t$ -balanced $m$ -splitting ${\mathcal P}=\{P_0,\ldots ,P_{m-1}\}$ of $H$ , that is suitable for $P_0$ and such that $V({\mathcal P})$ admits a viable partition ${\mathcal X}=\{X_1,\ldots ,X_{T}\}$ . By the definition of $\mathcal X$ being viable (Definition 3.9), we have that there exists a rerouting $\mathcal{R}=\{\{v^i_a,v^i_b\} \, : \, i=1,\ldots ,m\}$ of $\mathcal P$ and some partition of $\mathcal{R}$ as $\mathcal{R}=\mathcal{R}_1\cup \cdots \cup \mathcal{R}_{T}$ with $|\mathcal{R}_h|=\tilde {m}$ and $\mathcal{R}_h\subset \binom {X_h}{2}$ for each $h\in [T]$ . Moreover, as $\mathcal X$ is a viable (and hence transverse) partition of $V({\mathcal P})$ of size $T$ we necessarily have that for each $h\in [T]$ and each $i=0,\ldots ,m-1$ , the intersection $X_h\cap V(P_i)$ contains a single vertex. We label the vertices of each $X_h$ as $X_h=\{u_{0,h},\ldots ,u_{m-1,h}\}$ so that $u_{i,h}\in V(P_i)$ for $i=0,\ldots , m-1$ . We further set $\hat X_h\,:\!=\,X_h\setminus \{u_{0,h}\}=\{u_{i,h}:i\in [m-1]\}$ to be the vertex set obtained from $X_h$ by removing $u_{0,h}\in V(P_0)$ .

Our aim is to show that there is some feasible $(P_0,H)$ -switching $({\mathcal P},H',{\mathcal P}')$ . We will do this by finding a collection $\mathcal{C}_h$ of paths in $X_h$ , for $h\in [T]$ in succession. For each $h$ , we will guarantee the following properties of $\mathcal{C}_h$ :

1. (1) $\mathcal{C}_h$ is a path tiling in $G[X_h]$ , that is, the collection of paths in $\mathcal{C}_h$ are vertex-disjoint and cover the vertex set $X_h$ ;

2. (2) The set of pairs of endpoints $\{V^E(P) \, : \, P\in \mathcal{C}_h\}$ is precisely set $\mathcal{R}_h$ and each path in $\mathcal{C}_h$ has length at most $2t$ .

For the next conditions we define $\hat {\mathcal{C}_h}\,:\!=\,\{P[\hat X_h] \, : \, P\in \mathcal{C}_h\}$ to be the collection of paths obtained from $\mathcal{C}_h$ after deleting the vertex $u_{0,h}\in X_h$ and the edges that contain it. Note that by removing $u_{0,h}$ , one of the paths in $\mathcal{C}_h$ might split into two paths in $\hat {\mathcal{C}}_h$ . When we refer to edges in $\hat {\mathcal{C}}_h$ , we mean the collection of edges that feature on some subgraph belonging to the set $\hat {\mathcal{C}}_h$ .

1. (3) No edge in $\hat {\mathcal{C}}_h$ shares a colour with an edge in $H[V(G)\setminus V({\mathcal P}^I)]$ ;

2. (4) No edge in $\hat {\mathcal{C}}_h$ shares a colour with an edge in $\cup _{1\leq h'\lt h}\hat {\mathcal{C}}_{h'}$ ;

3. (5) The subgraph of $G$ obtained by taking all edges in $\hat {\mathcal{C}}_h$ is rainbow.

We claim that after finding such $\mathcal{C}_h$ , for all $h\in [T]$ , we will be done. Indeed, note that the graph obtained by taking $H[V(G)\setminus V({\mathcal P})]$ and all the paths in ${\mathcal P}'\,:\!=\,\cup _{h=1}^{T}\{P \, : \, P\in \mathcal{C}_h\}$ , defines a new loose Hamilton cycle $H'$ in $G$ , using here the conditions (1) and (2) above, and the fact that $\mathcal{R}$ is a rerouting as in Definition 3.8. Moreover, by (2), note that ${\mathcal P}'$ is an $m$ -splitting of $H'$ which is $2t$ -bounded. Note also that $H'[V(G)\setminus V^I({\mathcal P}')]$ is precisely the graph $H[V(G)\setminus V^I({\mathcal P})]$ and that $V(P_0)$ is transverse with respect to ${\mathcal P}'$ as the partition $\mathcal X$ was transverse with respect to $\mathcal P$ and all the paths in ${\mathcal P}'$ lie in one part of $\mathcal X$ . Thus the triple $({\mathcal P},H',{\mathcal P}')$ defines a $(P_0,H)$ -switching of size $m$ (as defined in Definition 3.3). Furthermore, the graph $F'\,:\!=\,H'[V({\mathcal P}')\setminus V(P_0)]$ is rainbow due to the conditions (4) and (5) and no edge in $F'$ shares a colour with an edge in $H[V(G)\setminus V({\mathcal P}^I)]$ due to the conditions given by (3). Hence $({\mathcal P},H',{\mathcal P}')$ is a feasible $(P_0,H)$ -switching, as required.

It remains to prove that we can find the collections $\mathcal{C}_h$ as claimed and as previously mentioned, we will show how to construct these sequentially for $h=1,\ldots ,T$ . So suppose that we are at the point of constructing $\mathcal{C}_h$ for some $h\in [T]$ and that all $\mathcal{C}_{h'}$ with $1\leq h'\lt h$ have already been constructed. Firstly, we let $G'\subset G[X_h]$ be the $k$ -graph obtained from $G[X_h]$ by deleting any edge $e\subset \hat X_h=X_h\setminus \{u_{0,h}\}$ that shares a colour with some edge in $H$ . Note that as $\mathcal P$ is a suitable splitting of $H$ and $\mathcal X$ is a viable partition, we have that $\delta _j(G')\geq (\delta _j^k(1)+\tfrac {\varepsilon }{4})m^{k-j}$ . Indeed, for any subset $S\subset X_h$ with $|S|=j$ , property (b) of Definition 3.9 implies that $S$ is contained in at least $(\delta _j^k(1)+\tfrac {\varepsilon }{2})m^{k-j}$ edges in $G[X_h]$ and property (i) of Definition 3.6 implies that at most $\tfrac {\varepsilon }{4} m^{k-j}$ of these share a colour with some edge in $H$ . We will find our paths in $G'$ and thus ensure that property (3) holds.

Next we define a (2-uniform) graph $B_h$ with vertex set $V(B_h)=X_h=\{u_{0,h},\ldots ,u_{m-1,h}\}$ and a pair of vertices $\{u_{i,h},u_{i',h}\}\in \binom {X_h}{2}$ being an edge of $B_h$ if and only if $0\notin \{i,i'\}$ and there is some $1\leq h'\lt h$ such that the pair $\{u_{i,h'},u_{i',h'}\}$ lies in an edge $e\in E(G[\hat X_{h'}])$ that features in $\hat {\mathcal{C}}_{h'}$ . We claim that $\Delta (B_h)\leq 2tk^2$ . Indeed, for a vertex $u=u_{i,h}\in X_h$ we have that $\deg _{B_h}(u)=0$ if $i=0$ and otherwise we bound the number of choices for $i'$ with $\{u,u_{i',h}\}\in E(B_h)$ by a choice of $h'\lt h$ (at most $t(k-1)\leq tk$ choices), a choice of edge $e\in G[\hat X_{h'}]$ that lies in $\hat {\mathcal{C}}_h\subset \mathcal{C}_h$ and contains $u_{i,h'}$ (at most 2 choices) and a choice of vertex $u_{i',h'}$ that lies in $e$ (at most $k-1\leq k$ choices).

By the ‘moreover’ part of Lemma 5.1, we can obtain a collection $\mathcal{C}_h$ of $\tilde {m}$ paths in $G'[X_h]$ that satisfy the conditions (1) and (2) above and such that no edge in a path in $\mathcal{C}_h$ contains an edge of $B_h$ . It remains to establish properties (4) and (5). For (5), note that as $\hat {\mathcal{C}}_h$ is a collection of vertex-disjoint loose paths, any pair of edges $e,f\subseteq \hat X_h\subset V({\mathcal P})\setminus V(P_0)$ that feature in $\hat {\mathcal{C}}_h$ necessarily have that $|e\cap f|\leq 1$ . Thus, as $\hat X_h$ is transverse with respect to $\mathcal P$ , we have that $\chi (e)\neq \chi (f)$ due to conditions (ii) (for $|e\cap f|=1$ ) and (iii) (for $|e\cap f|=0$ , see Remark 3.7) of Definition 3.6 and the fact that $\mathcal P$ is suitable for $P_0$ . This establishes (5). Finally, for (4) suppose for a contradiction that there is some edge $e$ in $\hat {\mathcal{C}}_h$ that shares a colour with some edge $f$ in $\hat {\mathcal{C}}_{h'}$ for some $1\leq h'\lt h$ . As $\mathcal P$ is suitable for $P_0$ and $e,f\subset V({\mathcal P})\setminus V(P_0)$ are disjoint edges that are both transverse with respect to $\mathcal P$ (as they lie in different parts of the transverse partition $\mathcal X$ ), condition (iii) of Definition 3.6 implies that there exists distinct $i,i'\in [m-1]$ such that $u_{i,h'},u_{i',h'}\subset f$ and $u_{i,h},u_{i',h}\subset e$ . However, this implies that $\{u_{i,h},u_{i',h}\}\in E(B_h)$ contradicting the fact that no edge on a path in $\mathcal{C}_h$ , contains an edge of $B_h$ . This concludes the proof.