2.1 Definitions and notations

For notations not defined in this paper, we refer the reader to [Reference Bang-Jensen and Gutin3]. Let $D=(V, A)$ be a digraph. The out-neighbourhood (resp., in-neighbourhood) of a vertex $v$ in $D$ is defined as $N^{+}(v)=\{u\,:\, vu\in A\}$ (resp., $N^{-}(v)=\{w\,:\, wv\in A\}$ ). The out-degree (resp., in-degree) of $v$ in $D$ , which is denoted by $d^+(v)$ (resp., $d^-(v)$ ), is the cardinality of $N^{+}(v)$ (resp., $N^{-}(v)$ ), that is, $d^{+}(v)=|N^{+}(v)|$ (resp., $d^{-}(v)=|N^{-}(v)|$ ). The minimum out-degree $\delta ^+(D)=\min \{d^{+}(v)\,:\, v\in V\}$ and the minimum in-degree $\delta ^-(D)=\min \{d^{-}(v)\,:\, v\in V\}$ . For any $X\subseteq V$ and $\sigma \in \{-, +\}$ , we define $N^\sigma (u, X)=N^\sigma (u)\cap X$ and $d^\sigma _X(u)=|N^\sigma (u, X)|$ for any vertex $u$ in $V$ . The cardinality of $X$ is denoted by $|X|$ , and we say $X$ is an $i$ -set if $|X|=i$ . The subdigraph of $D$ induced by $X$ is denoted as $D[X]$ . For another vertex set $Y$ that is not necessarily disjoint from $X$ , we use $e^+(X, Y)$ to represent the number of arcs from $X$ to $Y$ .

Given digraphs $D$ and $H$ , let $\mathcal{P}(D)$ be the family of paths in $D$ . An $H$ -subdivision in $D$ is a pair of mappings $f\,:\, V(H)\rightarrow V(D)$ and $g\,:\, A(H)\rightarrow \mathcal{P}(D)$ such that $(a)$ $f(u)\neq f(v)$ for $u, v\in V(H)$ with $u\neq v$ , and $(b)$ for every arc $uv\in A(H)$ , $g(uv)$ is a path from $f(u)$ to $f(v)$ , and different arcs are mapped into internally vertex-disjoint paths in $D$ .

We define the number of arcs of a path as its length and a $k$ -path refers to a path of order $k$ . We often represent the $k$ -path $P$ as $v_1\cdots v_k$ when $V(P)=\{v_1, \ldots , v_k\}$ and call $v_1$ and $v_k$ the initial and the terminal of $P$ , respectively. Furthermore, for two disjoint vertex sets $X$ and $Y$ in $V$ , if the initial and the terminal of $P$ belongs to $X$ and $Y$ , respectively, then we say that $P$ is an $(X, Y)$ -path. In particular, we write an $X$ -path instead of $(X, X)$ -path if $X=Y$ . Additionally, we say an $(X, Y)$ -path $P$ is minimal if there is no $(X, Y)$ -path $P^{\prime }$ with $|V(P^{\prime })|\lt |V(P)|$ . All paths in digraphs refer to directed paths, and we use the term disjoint instead of vertex-disjoint for simplicity. Given a family of graphs $\mathcal{F}$ , denote by $|\mathcal{F}|$ the number of graphs in $\mathcal{F}$ and we write $V(\mathcal{F})=\bigcup _{T\in \mathcal{F}}V(T)$ .

For a positive integer $t$ , we simply write $\{1, \ldots , t\}$ as $[t]$ . Throughout this paper, we will omit floor and ceiling signs when they are not essential. For the real numbers $a$ and $b$ , we use $a\pm b$ to represent an unspecified real number in the interval $[a-b, a+b]$ .

To summarise this subsection, we provide the following extremal condition for a constant $\varepsilon ^{\prime }$ , where $0\lt \varepsilon ^{\prime }\ll 1$ . In particular, we say the digraph $D$ is stable with parameter $\varepsilon ^{\prime }$ (for simplicity, $\varepsilon ^{\prime }$ -stable) if $D$ does not satisfy the following extremal condition (EC).

Extremal condition with parameter $\varepsilon ^{\prime }$ (EC( $\varepsilon ^\prime$ )): Let $D$ be a digraph of order $n$ . There exist two (not necessarily disjoint) vertex sets $U_1$ and $U_2$ in $D$ with $|U_i|\geq (1/2-\varepsilon ^\prime )n$ for every $i\in [2]$ such that $e^+(U_1, U_2)\leq (\varepsilon ^{\prime } n)^2$ .

Based on the extremal condition above, we now introduce a key combinatorial lemma concerning the internal structure of digraphs, which will serve as an essential technical tool in the analysis of host digraphs satisfying this condition.

For a digraph $H$ , a pair $(U_1, U_2)$ is called a bipartition of $H$ , written as $H=(U_1, U_2)$ , if $U_1\cap U_2=\emptyset$ and $U_1\cup U_2=V(H)$ , and $e(H)=e(U_1)\cup e(U_2)\cup e(U_1, U_2)$ . Here, $e(X)$ denotes the set of arcs in the induced subdigraph $H[X]$ with $X\in \{U_1, U_2\}$ , and $e(U_1, U_2)$ represents the arcs in the bipartite digraph $(U_1, U_2)$ . Furthermore, we also define the quantity $m_H=\min _{H=(U_1, U_2)}\big ||U_1|+e(U_2)-(|U_2|+e(U_1))\big |$ .

Proof. For a bipartition $(U_1, U_2)$ of $V(H)$ , define $f(U_1, U_2):=|U_1|+e(U_2)-(|U_2|+e(U_1))$ . Choose a bipartition $(U_1, U_2)$ such that $|f(U_1, U_2)|$ is minimal. Suppose for a contradiction that $|f(U_1, U_2)|\gt h/2-1$ . Since $|f(U_1, U_2)|$ is an integer, this implies $|f(U_1, U_2)|\geq \left \lfloor h/2\right \rfloor \geq 1$ . By swapping $U_1$ and $U_2$ if necessary, we may assume that $t:=f(U_1, U_2)\gt 0$ .

Claim 2.2. Every vertex in $U_1$ has total degree at least $2$ .

Proof. Let $u\in U_1$ . Moving $u$ from $U_1$ to $U_2$ yields a new bipartition $(U_1^{\prime }, U_2^{\prime })$ . The change in $f$ is $f(U_1^{\prime }, U_2^{\prime })=f(U_1, U_2)+ d(u)-2=t+d(u)-2$ . By the minimality of $|f(U_1, U_2)|$ , we have $|t+d(u)-2|\geq t$ . Hence, either $d(u)-2\geq 0$ or $d(u)-2\leq -2t$ . If the latter holds, then $d(u)\leq 2-2t\leq 0$ (since $t\geq 1$ ), contradicting the assumption that $\delta (H)\geq 1$ . Therefore, $d(u)\geq 2$ for all $u\in U_1$ .

Claim 2.3. Every vertex in $U_2$ has total degree at most $2$ .

Proof. Let $v\in U_2$ . Moving $v$ from $U_2$ to $U_1$ yielding a bipartition $(U_1^{\prime \prime }, U_2^{\prime \prime })$ with $f(U_1^{\prime \prime }, U_2^{\prime \prime })=t+2-d(v)$ . Again, the minimality implies $|t+2-d(v)|\geq t$ . Thus, either $2-d(v)\geq 0$ or $2-d(v)\leq -2t$ . If the latter holds, then $d(v)\geq 2+2t$ . Recalling that $t\geq \left \lfloor h/2\right \rfloor$ , we get $d(v)\geq 2t+2\geq 2\left \lfloor h/2\right \rfloor +2\gt h$ , which contradicts the obvious fact that $d(v)\leq e(H)=h$ . Hence, $d(v)\leq 2$ for all $v\in U_2$ .

Since each arc in $U_1$ contributes $2$ to $\sum _{u\in U_1} d(u)$ , each arc in $U_2$ contributes $2$ to $\sum _{v\in U_2} d(v)$ , and each crossing arc contributes $1$ to each sum, we have

\begin{align*} \sum _{u\in U_1} d(u)=2e(U_1)+e(U_1, U_2),\quad \mbox{and}\quad \sum _{v\in U_2} d(v)=2e(U_2)+e(U_1, U_2). \end{align*}

Combining these with the degree bounds from Claims 2.2 and 2.3, we obtain that

(2.1) \begin{align} \ &2|U_1|\leq \sum _{u\in U_1} d(u)=2e(U_1)+e(U_1, U_2),\quad \mbox{and} \\[-10pt] \nonumber\end{align}

(2.2) \begin{align} &\sum _{v\in U_2} d(v)=2e(U_2)+e(U_1, U_2)\leq 2|U_2|. \\[12pt] \nonumber\end{align}

Recall that $h=e(H)=e(U_1)+e(U_2)+e(U_1, U_2)$ and $t=f(U_1, U_2)=|U_1|+e(U_2)-(|U_2|+e(U_1))$ . We now derive bounds on the number of vertices $|V(H)|=|U_1|+|U_2|$ . From equation (2.1), we have $e(U_1, U_2)\geq 2|U_1|-2e(U_1)$ . Substituting into the expression for $h$ gives $h\geq e(U_1)+e(U_2)+2|U_1|-2e(U_1)=e(U_2)-e(U_1)+2|U_1|$ . Using the definition of $t$ , we have $e(U_2)-e(U_1)=t-|U_1|+|U_2|$ . Hence, $h\geq t-|U_1|+|U_2|+2|U_1|=t+|U_1|+|U_2|$ . So, $|V(H)|{\leq} {h-t}$ .

Similarly, for equation (2.2) we obtain $e(U_1, U_2)\leq 2|U_2|-2e(U_2)$ . Substituting into $h$ yields $h\leq e(U_1)+e(U_2)+2|U_2|-2e(U_2)=e(U_1)-e(U_2)+2|U_2|$ . Since $e(U_1)-e(U_2)=|U_1|-|U_2|-t$ , we get $h\leq |U_1|-|U_2|-t+2|U_2|=|U_1|+|U_2|-t$ . So $|V(H)|\geq h+t$ . Hence, we obtain $h+t\leq |V(H)|\leq h-t$ , which implies $t\leq 0$ . However, by our assumption for contradiction, we have $t\gt 0$ . Thus we have a contradiction. Therefore, the assumption is false, and we must have $t\leq \frac {h}{2}-1$ . This completes the proof.

Observation. The upper bound $h/2-1$ in Lemma 2.1 is tight. This can be seen by considering the case where $H$ is a $2$ -cycle. Then $m_H=0$ and $h/2-1=0$ , which shows that the bound cannot be reduced further.

2.2 Proof structure for the main theorems

Let $H$ be a digraph with $h$ arcs and $\delta (H)\geq 1$ , and let $D$ be a digraph as described in Theorems 1.3 and 1.5. Since the proofs of Theorem 1.3 and Theorem 1.5 follow a similar line of reasoning, we will only present the detailed proof strategy for Theorem 1.3. The proof of Theorem 1.3 utilises the stability method, which is divided into two main cases:

The extremal case, when the digraph $D$ is not $\varepsilon ^{\prime }$ -stable;

The non-extremal case, when $D$ is $\varepsilon ^{\prime }$ -stable.

• • Non-extremal case

For the non-extremal case, we divide the proof into the following two steps:

Step 1. Absorbing Lemma (Construction of an $H$ -subdivision subdigraph). By the extremal condition with parameter $\varepsilon$ and the probabilistic method, we construct an absorbing subdigraph $H^{\prime }$ that is a subdivision of $H$ and possesses the remarkable property that for every vertex pair $(u, v)$ in $D-H^{\prime }$ , every ‘long’ subdivided path inside $H^{\prime }$ contains at least one absorber for $(u, v)$ .

Step 2. Path-Covering Lemma (Lemma 3.6 in Subsection 3.1). This lemma allows us to cover all vertices of $D-H^{\prime }$ with a bounded number of disjoint paths of arbitrary prescribed lengths.

Finally, by exploiting the absorbing property of $H^{\prime }$ , we will absorb these disjoint paths of suitable lengths into $H^{\prime }$ to obtain the desired spanning $H$ -subdivision. This completes the proof for the non-extremal case.

The proof of Theorem 1.5 differs from that of Theorem 1.3 only in Step $1$ . Suppose that $n_1\geq \cdots \geq n_t\geq \alpha n\gt n_{t+1}\geq \cdots \geq n_m$ . Then we will construct $t$ disjoint absorbing $H$ -subdivisions $H_1^{\prime }, \ldots , H_t^\prime$ of orders are at most $n_1, \ldots , n_t$ , respectively, and subsequently construct $(m-t)$ disjoint $H$ -subdivisions, whose orders are $n_{t+1}, \ldots , n_m$ , respectively.

• • Extremal case

Step 3. For the extremal case, we show via the conventional structural method that $D$ satisfies one of three extremal structures: EC1( $\varepsilon$ ), EC2( $\varepsilon$ ), or EC3( $\varepsilon , \varepsilon _1$ ). Their descriptions are as follows.

In EC1( $\varepsilon$ ), with $O(\varepsilon n)$ exceptional vertices, the remaining vertices can be partitioned into two almost equal subsets $W_1$ , $W_2$ such that each $D[W_i]$ is almost complete. In EC2( $\varepsilon$ ), analogously, after removing few exceptional vertices, the vertex set partitions into two almost equal subsets $W_1$ , $W_2$ that form an almost complete bipartite digraph. In EC3( $\varepsilon$ , $\varepsilon _1$ ), again with few exceptional vertices, the remaining vertices of $V(D)$ can be partitioned into four disjoint vertex sets $W_1$ , $W_2$ , $W_3$ , and $W_4$ such that $|W_1|\approx |W_3|$ and $|W_2|\approx |W_4|$ ; here, $D[W_1]$ and $D[W_3]$ are almost complete, and $(\!W_2, W_4)$ is an almost complete bipartite digraph.

The proofs of Theorems 1.3 and 1.5 are completed in each extremal case through a detailed structural analysis.

3.1 Absorbing and path-covering lemmas

Let $C_0\gt 0$ be a constant and $C$ be any integer with $C\geq C_0$ , as shown in Theorems 1.3 and 1.5. Parameters $\varepsilon ^{\prime }, \rho$ and $\gamma$ are chosen such that

\begin{equation*}0\lt 1/C\ll \gamma \ll\rho\ll \varepsilon ^{\prime }\ll 1.\end{equation*}

The following standard inequalities will be frequently used.

For a vertex pair $(u, v)$ (possibly, $u=v$ ), we say that a $4$ -path $z_1z_2z_3z_4$ absorbs $(u, v)$ if $z_2u, vz_3\in A$ . Also, a $4$ -path is called an absorber for $(u, v)$ if it absorbs $(u, v)$ . This terminology reflects the fact that the $4$ -path $z_1z_2z_3z_4$ can be extended by absorbing a path with end-vertices $u$ and $v$ , resulting in a longer path with the same set of end-vertices. We say that a set $F$ of disjoint subdigraphs absorbs a family $U$ of vertex pairs if for every pair in $U$ , there exists a $4$ -path in $F$ that absorbs it, and the absorbing $4$ -paths for distinct vertices are distinct. Finally, for any vertex pair $(u, v)$ (possibly $u=v$ ) in $D$ , we denote by $\mathcal{A}_{uv}$ the family of all $4$ -paths absorbing $(u, v)$ . Then, we can conclude that for any vertex pair of $D$ , there are at least $\gamma n^4$ different $4$ -paths to absorb it.

Proof. Let $U_1=N^-(u)$ and $U_2=N^+(v)$ . By the lower bound of $\delta ^0(D)$ , we have that $|U_i|\geq (1/2-\rho )n$ for every $i\in [2]$ . Since $D$ is $\varepsilon ^{\prime }$ -stable, we obtain that $e^+(U_1, U_2)\gt (\varepsilon ^{\prime } n)^2$ . Then again by the lower bound of $\delta ^0(D)$ , we can deduce that for any given arc $z_2z_3$ with the vertex $z_2\in U_1$ and $z_3\in U_2$ , we have that $|N^-(z_2)\setminus \{u, v, z_3\}|\geq (1/2-\rho )n-3$ and $|N^+(z_3)\setminus \{u, v, z_2\}|\geq (1/2-\rho )n-3$ . This implies that the number of $4$ -paths $z_1z_2z_3z_4$ with $z_1\in N^-(z_2)\setminus \{u, v, z_3\}$ and $z_4\in N^+(z_3)\setminus \{u, v, z_1, z_2\}$ absorbing $(u, v)$ is at least

\begin{align*} \begin{split} (\varepsilon ^{\prime } n)^2\cdot ((1/2-\rho )n-3)\cdot ((1/2-\rho )n-4)\geq (\varepsilon ^{\prime })^2n^4/5\geq \rho n^4. \end{split} \end{align*}

This completes the proof of Fact 3.2.

Before presenting the absorption lemma, it is necessary to introduce the following useful lemmas. Lemma 3.3 below states that for a digraph $D$ with sufficiently large minimum semi-degree, we can get a small set $\mathcal{F}$ of disjoint absorbers, satisfying that for any vertex pair $(u, v)$ in $D$ , there are enough absorbers in $\mathcal{F}$ to absorb $(u, v)$ . Further, Lemma 3.4 below shows that we can partition this set $\mathcal{F}$ into $l$ disjoint parts such that in each part, there is at least one absorber for any vertex pair $(u, v)$ , and that for each part, by using some vertices in $V(D-\mathcal{F})$ and the extremal condition with parameter $\varepsilon$ (EC( $\varepsilon$ )), we can get a path covering all absorbers of this part.

Proof. Let $\gamma _1$ be a real number such that $\gamma _1^2/4\geq \gamma$ and $16\gamma _1^3\leq \gamma$ . We select a family $\mathcal{F}^{\prime }$ of ordered $4$ -sets from $[V(D)]^4$ at random by including each of $n(n-1)(n-2)(n-3)\sim n^4$ of them independently with probability $\gamma _1^3 n^{-3}$ (some of the selected $4$ -sets may not be absorbing at all). By Chernoff’s inequality, since $\mathbb{E}|\mathcal{F}^{\prime }|=n^4\cdot \gamma _1^3 n^{-3}=\gamma _1^3n$ , we have:

\begin{equation*}\mathbb{P}(|\mathcal{F}^{\prime }|\geq 2\gamma _1^3n)\leq \mathbb{P}(||\mathcal{F}^{\prime }|-\mathbb{E}|\mathcal{F}^{\prime }||\geq \gamma _1^3n)\leq 2e^{-\frac {1}{3}\mathbb{E}|\mathcal{F}^{\prime }|}.\end{equation*}

Similarly, for every vertex pair $(u, v)$ , by Fact 3.2 applied with $\rho=\gamma_1$ , we get that $\mathbb{E}|\mathcal{A}_{uv}\cap \mathcal{F}^{\prime }|=\gamma_1 n^4\cdot \gamma _1^3 n^{-3}=\gamma _1^4n$ . So by Chernoff’s inequality again, we have that $\mathbb{P}(|\mathcal{A}_{uv}\cap \mathcal{F}^{\prime }|\leq \gamma _1^4n/3)\leq \mathbb{P}(||\mathcal{A}_{uv}\cap \mathcal{F}^{\prime }| -\mathbb{E}|\mathcal{A}_{uv}\cap \mathcal{F}^{\prime }||\geq \gamma \gamma _1^3n-\gamma _1^4n/3)\leq 2e^{-\frac {1}{12}\mathbb{E}|\mathcal{A}_{uv}\cap \mathcal{F}^{\prime }|}$ . Thus, with probability $1-o(1)$ , as $n\rightarrow \infty$ :

$(1)$ $|\mathcal{F}^{\prime }|\lt 2\gamma _1^3n\leq \gamma n$ , and $|\mathcal{A}_{uv}\cap \mathcal{F}^{\prime }|\gt \gamma _1^4n/3$ for every vertex pair $(u, v)$ .

Clearly, the expected number of intersecting pairs of $4$ -sets in $\mathcal{F}^{\prime }$ is at most

\begin{align*} \begin{split} n^4\times \big(C_4^1n^3+C_4^2n^2+C_4^3n\big)\times \big(\gamma _1^3 n^{-3}\big)^2\leq n^4\times 4\times 4\times n^3\times \big(\gamma _1^3 n^{-3}\big)^2=16\gamma _1^6n, \end{split} \end{align*}

so by Markov’s inequality: with $X:=$ the number of intersecting pairs of $4$ -sets in $\mathcal{F}^{\prime }$ and $a=17\gamma _1^6n$ , we can get that $\mathbb{P}(X\geq 17\gamma _1^6n)\leq \frac {\mathbb{E}X}{a}=\frac {16\gamma _1^6n}{17\gamma _1^6n}=16/17$ . This implies that

$(2)$ with probability at least $1/17$ , as $n\rightarrow \infty$ , there are at most $17\gamma _1^6n$ pairs of intersecting $4$ -sets in $\mathcal{F}^{\prime }$ .

Hence, with positive probability, the family $\mathcal{F}^{\prime }$ satisfies the properties both $(1)$ and $(2)$ , which implies that there exists one such family, and, for simplicity, we define this family to be $\mathcal{F}^{\prime \prime }$ . From $\mathcal{F}^{\prime \prime }$ we delete all $4$ -sets that intersect other $4$ -sets, as well as all $4$ -sets that are not absorbers, and denote by $\mathcal{F}$ the remaining subfamily. Clearly, by $(1)$ and $(2)$ again, we have that $|\mathcal{F}|\geq 2\gamma _1^3{n-17\gamma _1^6n\geq 3\gamma _1^3n/2}$ . Also, the family $\mathcal{F}$ consists of disjoint absorbers and by $(2)$ and $(1)$ , for every vertex pair $(u, v)$ ,

\begin{align*} \begin{split} |\mathcal{A}_{uv}\cap \mathcal{F}|\gt \frac {\gamma _1^4n}{3}-2\cdot 17\gamma _1^6n\gt \frac {\gamma _1^4n}{4}\geq \gamma ^2n. \end{split} \end{align*}

This completes the proof of the lemma.

For two paths $P=a\cdots b$ and $Q=b\cdots d$ with $V(P)\cap V(Q)=\{b\}$ , we denote the concatenated path as $P\circ Q$ . This definition can be extended naturally to more than two paths. Further, the following conclusion holds.

Proof. Recall that the parameters $\gamma _1, \gamma$ and $\varepsilon ^{\prime }$ satisfy $16\gamma _1^3\leq \gamma \ll \varepsilon ^{\prime }$ . In the following, we first prove (i), and second give the proof of (ii).

We prove that there exists a partition $\mathcal{F}=\mathcal{F}_1\cup \cdots \cup \mathcal{F}_l$ satisfying our conditions with high probability. Let $F_{uv}^{\,j}$ be a random variable that calculates the number of absorbers of $(u, v)$ in $\mathcal{F}_j$ for $j\in [l]$ . Since Lemma 3.3 gives $|\mathcal{A}_{uv}\cap \mathcal{F}|\geq \gamma ^2n$ and $|\mathcal{F}|\lt \gamma n$ , it is not hard to see that

\begin{align*} \begin{split} \mathbb{E}F_{uv}^{\,j}=\frac {|\mathcal{A}_{uv}\cap \mathcal{F}|}{|\mathcal{F}|}\cdot |\mathcal{F}_j| \geq \frac {\gamma ^2n}{\gamma n}\cdot |\mathcal{F}_j|=\gamma |\mathcal{F}_j|, \end{split} \end{align*}

Then by Chernoff’s bound with $a=\frac {1}{2}$ , for any $j\in [l]$ , due to $\beta f\leq |\mathcal{F}_j|\leq (1-\beta )f$ and $f\geq \gamma ^2n$ , we obtain that

(3.1) \begin{align} \mathbb{P}\left (F_{uv}^{\,j}\lt \frac {\mathbb{E}F_{uv}^{\,j}}{2}\right )\leq \mathbb{P}\left (\Big|F_{uv}^{\,j}-\mathbb{E}F_{uv}^{\,j}\Big| \gt \frac {\mathbb{E}F_{uv}^{\,j}}{2}\right ) \lt 2e^{-\frac {\mathbb{E}F_{uv}^{\,j}}{12}}\leq 2e^{-\frac {\gamma |\mathcal{F}_j|}{12}}. \end{align}

Notice that there are less than $n^2$ vertex pairs in $D-V(\mathcal{F})$ . Since $|\mathcal{F}|\geq |\mathcal{A}_{uv}\cap \mathcal{F}|\geq \gamma ^2n$ , we have that $|\mathcal{F}_j|\geq \beta f\geq \beta \gamma ^2n$ . Then by equation (3.1), for $j\in [l]$ , we get that

\begin{align*} \sum _{\{u, v\}\subseteq V(D-\mathcal{F})}\mathbb{P}\left (F_{uv}^{\,j}\lt \frac {\mathbb{E}F_{uv}^{\,j}}{2}\right ) \lt 2n^2e^{-\frac {\gamma |\mathcal{F}_j|}{12}}\leq 2n^2e^{-\frac {\beta \gamma ^3n}{12}}\rightarrow 0, \mbox{as} \ n\rightarrow \infty . \end{align*}

Therefore with high probability, we obtain that $F_{uv}^{\,j}\geq \frac {\mathbb{E}F_{uv}^{\,j}}{2}\geq \frac {\gamma |\mathcal{F}_j|}{2}\gt 0$ for any $j\in [l]$ . Recapping the definition of $F_{uv}^{\,j}$ , this implies that we may always find $l$ subsets $\mathcal{F}_1, \ldots , \mathcal{F}_l$ of absorbers in $\mathcal{F}$ such that for any vertex pair $(u, v)$ of $D-V(\mathcal{F})$ and any $i\in [l]$ , the family $\mathcal{F}_i$ contains at least one absorber of $(u, v)$ . This implies that (i) holds.

(ii) Let $\mathcal{F}_1\cup \cdots \cup \mathcal{F}_l$ be a partition of $\mathcal{F}$ satisfying (i). For any index $i\in [l]$ , we have that $|\mathcal{F}_i|=f_i$ . In the following, we will prove (ii) by induction on $k$ that for each $k\in [f_i]$ , there exists a path $S_k$ in $D$ of the form $S_1=F_{i, 1}$ and for $k\geq 2$ ,

\begin{align*} \begin{split} S_k=F_{i, 1}\circ P_{i, 1}\cdots \circ F_{i, k-1}\circ P_{i, k-1}\circ F_{i, k}, \end{split} \end{align*}

where each of the paths $P_{i, 1}, \ldots , P_{i, k-1}$ has the length at most $3$ . Note that $L_i=S_{f_i}$ .

It is obvious for the case $k=1$ . Assume that the equation above is true for some $k-1\in [f_i-1]$ . Moreover, we suppose that the terminal of $F_{i, k-1}$ is $b$ , and the initial of $F_{i, k}$ is $a$ . Denote by $D_{k-1}$ the subdigraph induced by the vertex set $V_{k-1}=V(D)\setminus V((S_{k-1}-b)\cup (\mathcal{F}-a))$ in $D$ . By the proof of Lemma 3.3, we have that $|\mathcal{F}|\leq 2\gamma _1^3 n$ , and then $|V(S_{k-1}\cup \mathcal{F})|\lt |\mathcal{F}|(4+4)=8f\leq 8\cdot 2\gamma _1^3 n\lt \gamma n$ . This implies that $|N^+_{D_{k-1}}(b)|, |N^-_{D_{k-1}}(a)|\geq \delta ^0(D)-|V(S_{k-1}\cup \mathcal{F})|\geq (1/2-2\gamma )n\gt (1/2-\varepsilon ^{\prime })n$ . Then by the extremal condition with $(U_1, U_2)_{EC(\varepsilon ^\prime )}=(N^+_{D_{k-1}}(b), N^-_{D_{k-1}}(a))$ , there is a path $P_{i, k-1}$ from $b$ to $a$ of length at most $3$ in $D_{k-1}$ such that it connects paths $S_{k-1}$ and $F_{i, k}$ . Note that $V(P_{i, k-1})\setminus \{a, b\}$ is disjoint from $V(\mathcal{F}\cup S_{k-1})$ , and so the desired path

\begin{align*} \begin{split} S_{k}=S_{k-1}\circ P_{i, k-1}\circ F_{i, k}. \end{split} \end{align*}

Hence, the proof of $(ii)$ is completed.

By using Lemmas 3.3 and 3.4, we will now present the following absorption lemma.

Lemma 3.5 (Absorbing Lemma).Suppose that $C\gt 0$ is an integer and $\alpha , \beta$ are two constants with $0\lt \alpha , \beta \ll 1$ . Let $n=n_1+\cdots +n_m$ with $n\geq Chm$ , $n_i\geq|V(H)|+3h$ for each $i\in[m]$ , and $\sum _{n_i\lt \alpha n}n_i\leq \beta n$ . For any digraph $H$ with the vertex set $V(H)=\{v_1, \ldots , v_s\}$ and $h$ arcs, and $\delta (H)\geq 1$ , if $D$ is a digraph with the order $n$ and $\delta ^0(D)\geq n/2$ , and $D$ is $\varepsilon ^{\prime }$ -stable, then the following statements hold.

$(i)$ For any sequence $\mathcal{N}=\{l_1, \cdots , l_h\}$ satisfying that each $l_i\geq3$ and the sum of the $l_i$ less than $\alpha n$ is not more than $\beta n$ , the digraph $D$ contains an $H$ -subdivision, called $H^{\prime }$ , with $|V(H^{\prime })|\leq \gamma n$ and in which the length of internally disjoint mapped paths is at most $l_1, \ldots , l_h$ , respectively.

$(ii)$ The digraph $D$ contains $m$ disjoint $H$ -subdivisions, called $H^{\prime }_1, \ldots , H^{\prime }_m$ , such that $|\bigcup _{i=1}^mV(H^{\prime }_i)|\leq 5\gamma n$ , and for each $i\in [m]$ , we have that $|V(H^{\prime }_i)|\leq n_i$ .

$(iii)$ Finally, we define the digraph $Q$ as follows:

\begin{align*} \begin{split} Q=\left \{ \begin{array}{ll} H^{\prime }, &\quad for\ (i),\\[3pt] H^{\prime }_1\cup \cdots \cup H^{\prime }_m, &\quad for\ (ii). \end{array} \right . \end{split} \end{align*}

In the constructions of (i) and (ii), $Q$ contains $t$ distinguished paths $L_1, \ldots, L_t$ , such that each $L_i$ contains an absorber for every vertex pair $(u, v)$ of $D-Q$ . Consequently, for any $t$ pairwise disjoint paths $P_1, \ldots, P_t$ in $D-Q$ , where $P_i$ has initial $c_i$ and terminal $d_i$ , the path $L_i$ can absorb $P_i$ for each $i\in[t]$ , and the same branch-vertices are maintained.

Proof. Suppose that $\gamma$ is a real number satisfying that

\begin{equation*}0\lt 1/C\ll \alpha , \beta, \gamma_1\lt \gamma \ll \varepsilon ^{\prime }.\end{equation*}

We shall repeatedly use the following simple observation. Since $D$ is $\varepsilon^\prime$ -stable, for any two vertex sets $X,Y\subseteq V(D)$ with $|X|,|Y|\geq(1/2-\varepsilon^\prime)n$ , we have $e_D^+(X,Y)\gt(\varepsilon^\prime n)^2$ . In particular, if $D^\prime$ is an induced subdigraph of $D$ obtained by deleting at most $\eta n$ vertices, where $\eta\ll \varepsilon^\prime$ , and $X, Y\subseteq V(D^\prime)$ still satisfy $|X|, |Y|\geq(1/2-\varepsilon^\prime)n$ , then since $D^\prime$ is induced, $e_{D^\prime}^+(X,Y)=e_{D}^+(X,Y)\gt(\varepsilon^\prime n)^2$ . Thus there is an arc from $X$ to $Y$ in $D^\prime$ . In the applications below, the number of deleted vertices is always at most $(\beta+O(\gamma)+O(1/C))n\ll \varepsilon^\prime n$ , so the relevant neighbourhoods, which have size $(1/2-o(\varepsilon^\prime))n$ before the deletion, still have size at least $(1/2-\varepsilon^\prime)n$ .

(i) Without loss of generality, we assume that $l_1\geq l_2\geq \cdots \geq l_h$ . Take $t$ from $[h]$ such that $t$ is the largest subscript satisfying $l_t\geq \alpha n$ . Note that $t$ is an absolute constant independent of $n$ since $t\leq \frac {n}{\alpha n}=\frac {1}{\alpha }$ . We define $W=f(V(H)):=\{u_1, \ldots , u_s\}$ and let $D^{\prime }=D-W$ . Clearly, $\delta ^0(D^\prime )\geq n/2-s\geq n/2-2h\geq (\frac {1}{2}-\frac {1}{Cm})n$ since $n\geq Chm$ .

On the one hand, in the desired $H$ -subdivision $H^{\prime }$ , if there is a path of length $l_{t+1}\lt \alpha n$ , say from $u_1$ to $u_2$ , then we can greedily get this path by doing the following. We choose a vertex $w_3\in N_{D^{\prime }}^+(u_1)$ and $w_{i+1}\in N^+_{D^{\prime }}(w_i)\setminus \{w_3, \ldots , w_i\}$ for all $i\in \{3, \ldots , l_{t+1}-3\}$ . Further, because $l_{t+1}+\cdots +l_h\leq \beta n$ and $\delta ^0(D^{\prime })\geq (\frac {1}{2}-\frac {1}{Cm})n$ , we have that $|N^+_{D^{\prime }}(w_{l_{t+1}-2})\setminus \{u_1, w_3, \ldots , w_{l_{t+1}-2}, u_2\}|, |N^-_{D^\prime }(u_2)\setminus \{u_1, w_3, \ldots , w_{l_{t+1}-2}, u_2\}|\geq (1/2-\varepsilon ^\prime )n$ . Then this implies that there is an arc from the former to the latter, since $D$ does not satisfy EC( $\varepsilon$ ) and $D^\prime \subseteq D$ . Using a similar process as shown below, we can obtain all paths $P_{t+1}, \ldots , P_h$ of length $l_{t+1}, \ldots , l_h$ , respectively, of the desired $H$ -subdivision $H^\prime$ .

In the following, let $D^{\prime \prime }=D^{\prime }-\bigcup _{j=t+1}^hP_j$ . Clearly, $\delta ^0(D^{\prime \prime })\geq (1/2-\beta )n$ . Then by Lemma 3.3, there is a family $\mathcal{F}$ of at most $\gamma n$ disjoint, absorbing $4$ -paths in $D^{\prime \prime }$ such that for every vertex pair $(u, v)$ , we have that $|\mathcal{A}_{uv}\cap \mathcal{F}|\geq \gamma ^2n$ . Then by using Lemma 3.4, we can partition $\mathcal{F}$ into $t$ distinct parts, say $\mathcal{F}_1, \ldots , \mathcal{F}_t$ , such that $|V(\mathcal{F}_i)|\leq l_i-6$ for each $i\in [t]$ , and in each part, there is an absorber for any vertex pair $(u, v)$ of $V(D^{\prime \prime }-\mathcal{F})$ , and Lemma 3.4 also depicts that we can connect all absorbing paths in $\mathcal{F}_i$ into a path $L_i$ of length no more than $l_i-6$ . Further, these paths $L_1, \ldots , L_t$ are disjoint and $|\bigcup _{i=1}^tV(L_i)|\leq \gamma n$ . Without loss of generality, write $L_i=a_i\cdots b_i$ for any $i\in [t]$ , and suppose that in the desired $H$ -subdivision $H^{\prime }$ , the path from $u_i$ to $u_i^{\prime }$ has the length at most $l_i$ . Define $D^0=D^{\prime \prime }-\bigcup _{j=1}^tL_j$ , and let $R_i=N_{D^0}^+(u_i)$ and $S_i=N_{D^0}^-(a_i)$ for each $i\in [t]$ . Then we have that $|R_i|, |S_i|\geq \delta ^0(D^{\prime \prime })-\gamma n\geq (1/2-\varepsilon ^{\prime })n$ , which implies that there exists an arc $x_ix_i^{\prime }$ from $R_i$ to $S_i$ , since $D^0\subset D$ does not meet EC( $\varepsilon$ ). Similarly, we can prove that there is an arc $y_iy_i^\prime$ from $N_{D^0}^+(b_i)$ to $N_{D^0}^-(u_i^\prime )$ for each $i\in [t]$ . Then we get a path $u_ix_ix_i^{\prime } L_iy_iy_i^{\prime } u_i^\prime$ . Hence we obtain all paths of length at most $l_1, \ldots , l_t$ , respectively.

To sum up, we get an $H$ -subdivision $H^{\prime }$ in $D$ , in which the length of internally disjoint mapped paths is at most $l_1, \ldots , l_h$ , respectively. Clearly, $|V(H^{\prime })|\leq \beta n+4h+|V(\mathcal{F})|\leq \gamma n$ . This completes the proof of (i).

(ii) In $D$ , we randomly take the disjoint mapping vertex sets of $V(H)$ to be $f_1(V(H))=W_1:=\{v_1^1, v_2^1, \ldots , v_s^1\}$ , …, $f_m(V(H))=W_m:=\{v_1^m, v_2^m, \ldots , v_s^m\}$ , respectively. Let $D^{\prime }=D-\cup _{i=1}^m W_i$ , and clearly, since $n\geq Chm$ ,

\begin{align*} \delta ^0(D^{\prime })\geq \frac {n}{2}-2mh\geq \frac {n}{2}-\frac {2n}{C}\geq (1/2-\beta )n. \end{align*}

Without loss of generality, we assume that $n_1\geq \cdots \geq n_t\geq \alpha n\gt n_{t+1}\geq \cdots \geq n_m$ . In the following, we will first get $t$ disjoint $H$ -subdivisions $H_1^{\prime }, \ldots , H_t^\prime$ of order at most $n_1, \ldots , n_t$ , respectively, such that $|\bigcup _{i=1}^tV(H_i^\prime )|\leq 4\gamma n$ . Second, we will prove that in the remaining digraph, there are $m-t$ disjoint $H$ -subdivisions, that the order of each such $H$ -subdivision is $n_{t+1}, \ldots , n_m$ , respectively.

First, similar to the proof of (i), Lemma 3.3 gives a family $\mathcal{F}$ of at most $\gamma n$ disjoint absorbers in $D^{\prime }$ such that for every vertex pair $(u, v)$ , it satisfies that $|\mathcal{A}_{uv}\cap \mathcal{F}|\geq \gamma ^2n$ . Then applying Lemma 3.4, we can partition the family $\mathcal{F}$ into $t$ disjoint subfamily, say $\mathcal{F}_1, \ldots , \mathcal{F}_t$ , such that for each $i\in [t]$ , $|V(\mathcal{F}_i)|\lt n_i$ , and further, all $4$ -paths in $\mathcal{F}_{i}$ can be connected into a path $L_i$ with $|V(L_i)|\lt n_i$ . Without loss of generality, assume that $L_i=a_i\cdots b_i$ for every $i\in [t]$ . For any $i\in [t]$ , in the desired $H$ -subdivision $H^{\prime }_i$ , the path, say from $v_1^i$ to $v_2^i$ , can be gotten by the following strategy as below. We define $D^{\prime \prime }=D^{\prime }-\bigcup _{j=1}^tL_j$ , and let $R_i=N_{D^{\prime \prime }}^+(v_1^i)$ and $S_i=N_{D^{\prime \prime }}^-(a_i)$ for each $i\in [t]$ . Then we have that $|R_i|, |S_i|\geq \delta ^0(D^{\prime \prime })\geq (1/2-\beta )n-\gamma n\geq (1/2-2\gamma )n$ , which implies that there exists an arc $x_1^ix_2^i$ from $R_i$ to $S_i$ , since $D^{\prime \prime }\subset D$ does not EC( $\varepsilon$ ). Similarly, we can prove that there is an arc $y_1^iy_2^i$ from $N_{D^{\prime \prime }}^+(b_i)$ to $N_{D^{\prime \prime }}^-(v_2^i)$ for each $i\in [t]$ . Then we get a path $v_1^ix_1^ix_2^iL_iy_1^iy_2^iv_2^i$ for any $i\in [t]$ . This can be done because $\delta ^0(D^{\prime \prime })-4t\geq (1/2-2\gamma )n-\frac {n}{Ch}\geq (1/2-3\gamma )n\gt 0$ . Let $D^3$ be the remaining digraph, and clearly $\delta ^0(D^3)\geq (1/2-3\gamma )n$ . Further, for the other paths in the desired $H$ -subdivision $H_i^{\prime }$ with $i\in [t]$ , we can obtain these paths of length at most $3$ . This is because by $|N_{D^3}^\sigma (v_j^i)|\geq \delta ^0(D^3)\gt \delta ^0(D^3)-2hm\geq (1/2-3\gamma )n-\frac {n}{C}\geq (1/2-7\gamma /2)n$ for any $\sigma \in \{+, -\}$ , $i\in [m]$ and $j\in [s]$ , and $D^3\subset D$ does not satisfy EC( $\varepsilon$ ), we get that there are at least $(\varepsilon ^{\prime } n)^2$ arcs from $N_{D^3}^\sigma (v_j^i)$ to $N_{D^3}^{-\sigma }(v_k^l)$ with $j, k\in [s]$ and $i, l\in [m]$ and $(U_1, U_2)_{EC(\varepsilon )}=(N_{D^3}^\sigma (v_j^i), N_{D^3}^{-\sigma }(v_k^l))$ . This suggests that we obtain $t$ disjoint $H$ -subdivisions $H_1^{\prime }, \ldots , H_t^{\prime }$ with $|\bigcup _{i=1}^tV(H_i^{\prime })|\leq 7\gamma n/2$ , and in which, the order of $H_1^{\prime }, \ldots , H_t^{\prime }$ is at most $n_1, \ldots , n_t$ , respectively.

Let $D^4=D^3-\bigcup _{i=1}^tH_i^{\prime }$ , and obviously $\delta ^0(D^4)\geq (1/2-7\gamma /2)n$ . In the following, we will prove that $D^4$ contains $m-t$ disjoint $H$ -subdivisions with the order $n_{t+1}, \ldots , n_m$ , respectively. Similar to the proof at the end of the previous paragraph, we can get that for each $i\in \{t+1, \ldots , m\}$ , there are $h-1$ disjoint paths of length at most $3$ as desired in the $H$ -subdivision $H_i^{\prime }$ , since for any vertex $v_l^k$ with $l\in [s], k\in [m]\setminus [t]$ , we have that

\begin{align*} \begin{split} \big|N_{D^4}^\sigma \big(v_l^k\big)\big|\geq \delta ^0(D^4)\gt \delta ^0(D^4)-2hm\geq (1/2-7\gamma /2)n-2n/C\geq (1/2-4\gamma )n. \end{split} \end{align*}

Finally, in every promised $H$ -subdivision $H_i^{\prime }$ with $i\in [m]\setminus [t]$ , only one path is missing, without loss of generality, say from $v_{h-1}^i$ to $v_h^i$ order $n_i^{\prime }$ . Let $D^5$ be the remaining digraph, and then clearly, $\delta ^0(D^5)\geq \delta ^0(D^4)-2hm\geq (1/2-4\gamma )n$ since $n\geq Chm$ and $1/C\ll \gamma$ . Then we can greedily get these paths by doing the following. Let $i$ be any index with $i\in [m]\setminus [t]$ . We choose a vertex $w_3\in N_{D^5}^+(v_{h-1}^i)$ and $w_{j+1}\in N^+_{D^5}(w_j)\setminus \{w_3, \ldots , w_j\}$ for all $j\in \{3, \ldots , n_i^{\prime }\}$ . Further, because $n_{t+1}^{\prime }+\cdots +n_m^{\prime }\leq \beta n$ and $\delta ^0(D^5)\geq (1/2-4\gamma )n$ , we have that $\!|N^+_{D^5}(w_{n_{i}^{\prime }-2})\setminus \{v_{h-1}^i, w_3, \ldots , w_{n_{i}^{\prime }-2}, v_{h}^i\}|, |N^-_{D^{\prime }}(v_{h}^i)\setminus \{v_{h-1}^i, w_3, \ldots , w_{n_{i}^\prime -2}, v_{h}^i\}|\geq (1/2-4\gamma )n$ . Let $R$ be the previous set and $S$ be the subsequent set. Then this implies that there is an arc from $R$ to $S$ , since $D$ does not satisfy EC( $\varepsilon$ ) and $D^5\subseteq D$ . Using a similar process as shown below, we can obtain all paths of order $n_{t+1}^{\prime }, \ldots , n_m^{\prime }$ , of the desired $H$ -subdivisions $H_{t+1}^{\prime }, \ldots , H_{m}^{\prime }$ , respectively, due to

(3.2) \begin{equation} \begin{split} \delta ^0(D^5)-(n_{t+1}^{\prime }+\cdots +n_m^{\prime })\geq (1/2-4\gamma )n-\beta n\geq (1/2-5\gamma )n. \end{split} \end{equation}

Hence we get $m-t$ disjoint $H$ -subdivisions of order $n_{t+1}, \ldots , n_m$ , respectively.

So we get $m$ disjoint $H$ -subdivisions $H_1^{\prime }, \ldots , H_m^\prime$ such that $|V(H_i^\prime )|\lt n_i$ for $n_i\geq \alpha n$ and $|V(H_i^\prime )|=n_i$ for $n_i\lt \alpha n$ . Also, by equation (3.2), we have that $|\bigcup _{i=1}^mV(H_i^\prime )|\leq 5\gamma n$ . This implies that (ii) is true.

(iii) In the following, we will prove that $Q$ captures the desired absorption property. By Lemma 3.4 and the constructions of $H^{\prime }_1, \ldots , H^\prime _m$ , for each $i\in [t]$ ( $t$ is defined in $(ii)$ . Also, maybe $t=0$ and in the case, it is $H^\prime$ ), the distinguished path $L_i$ contains an absorber for every vertex pair $(u, v)\in D-Q$ .

Let $P_1, \ldots, P_t$ be pairwise disjoint paths in $D-Q$ , where $P_i=c_i\cdots d_i$ for each $i\in[t]$ . For each $i\in[t]$ , choose an absorber $z_1z_2z_3z_4$ for $(c_i, d_i)$ contained in $L_i$ . Since $z_2c_i, d_iz_3\in A(D)$ , we can replace the subpath $z_1z_2z_3z_4$ of $L_i$ by $z_1z_2P_iz_3z_4$ . This absorbs $P_i$ into $L_i$ without changing the initial and terminal of $L_i$ . Since the paths $P_1, \ldots, P_t$ are pairwise disjoint and are disjoint from $Q$ , all these replacements can be performed simultaneously. Hence all branch-vertices of $H^\prime$ or $(H_1^\prime, \ldots, H^\prime_m$ remain unchanged. So (iii) holds.

Hence we complete the proof of this lemma.

Let $\nu$ and $\tau$ be real numbers with $0\lt \nu \leq \tau \lt 1$ . Suppose that $D$ is a digraph and $S$ is a vertex subset of $V(D)$ . The $\nu$ -robust out-neighbourhood $RN^+_{\nu , D}(S)$ of $S$ is defined as the set of all vertices $x$ in $D$ that have at least $\nu |V(D)|$ in-neighbourhoods in $S$ . Moreover, the digraph $D$ is called a robust $(\nu , \tau )$ -outexpander if $|RN^+_{\nu , D}(S)|\geq |S|+\nu |V(D)|$ for all $S\subseteq V(D)$ with $\tau |V(D)|\lt |S|\lt (1-\tau )|V(D)|$ . Kühn, Osthus and Treglown [Reference Kühn, Osthus and Treglown18] depicted that for a positive integer $n_0$ and $1/n_0\ll \nu \leq \tau \ll \xi \lt 1$ , if $D$ is a digraph on $n\geq n_0$ vertices with $\delta ^0(D)\geq \xi n$ and is a robust $(\nu , \tau )$ -outexpander, then $D$ contains a Hamiltonian cycle.

In particular, if $D$ is a digraph with $\delta ^0(D)\geq (1/2-\varepsilon ^{\prime })n$ , where $0\lt \varepsilon ^{\prime }\ll \varepsilon \ll 1$ , and $D$ is $\varepsilon ^{\prime }$ -stable with parameter $\varepsilon$ , then we will prove that $D$ is a robust $(\nu , \tau )$ -outexpander, and so the following path-covering lemma holds. Since a detailed proof in our paper [Reference Cheng, Wang and Yan5] has been given, we will omit its proof here.

3.2 Completion of Theorems 1.3 and 1.5

In this subsection, we always assume that $H$ is any digraph with $\delta (H)\geq 1$ , and $D$ is an $n$ -vertex digraph $\delta ^0(D)\geq n/2$ , and $D$ is $\varepsilon ^{\prime }$ -stable. Let $C\gt 0$ be a constant, and take parameters $\alpha , \beta$ and $\gamma$ satisfy $0\lt 1/C\ll \alpha , \beta \lt \gamma \ll \varepsilon ^{\prime }\ll 1$ . We first give the proof of Theorem 1.3, and then we will prove Theorem 1.5.

Proof of Theorem 1.3. Let $\mathcal{N}=\{l_1, \ldots , l_h\}$ be any integer set with $l_1+\cdots +l_h\lt n$ . Without loss of generality, suppose that $l_1\geq \cdots \geq l_t\geq \alpha n\gt l_{t+1}\geq \cdots \geq l_h$ , and the sum of the $l_i$ less than $\alpha n$ is not more than $\beta n$ . By Lemma 3.5(i), we can obtain an $H$ -subdivision in $D$ , called $H^{\prime }$ , with $|V(H^{\prime })|\leq \gamma n$ , and in $H^\prime$ , the paths of length less than $\alpha n$ have reached the lengths as required in the desired $H$ -subdivision. However, for the paths of length at least $\alpha n$ , in $H^\prime$ , there are corresponding ‘long’ paths, defined as $Q_1, \ldots , Q_t$ , of length no more than $l_1, \ldots , l_t$ , respectively, and each of these long paths contains an absorber of any vertex pair $(u, v)$ in $D-H^\prime$ . With the aid of Lemma 3.6, we can divide the Hamiltonian path in $D-H^\prime$ into $t$ disjoint subpaths, defined $R_1, \ldots , R_t$ , such that for each $i\in [t]$ , $R_i=c_i\cdots d_i$ and the cardinality of $V(Q_i\cup R_i)$ is $l_i+1$ . Since the path $Q_i$ contains an absorber of the pair $(c_i, d_i)$ for any $i\in [t]$ , the path $Q_i$ can absorb $R_i$ to get a path with the same initial and terminal as $Q_i$ and the length $l_i$ as desired. Therefore, we get a spanning $H$ -subdivision, in which, the length of paths is $l_1, \ldots , l_h$ , respectively. This proves Theorem 1.3 for the non-extremal case.

Proof of Theorem 1.5. Let $n=n_1+\cdots +n_m$ be any integer partition of $n$ . Without loss of generality, we assume that $n_1\geq \cdots \geq n_t\geq \alpha n\gt n_{t+1}\geq \cdots \geq n_m$ , and the sum of the $n_i$ less than $\alpha n$ is no more than $\beta n$ . With the help of Lemma 3.5(ii), we can obtain $m$ disjoint $H$ -subdivisions $H^{\prime }_1, \ldots , H^{\prime }_m$ , such that for each $i\in [t]$ , we have $|V(H^{\prime }_i)|\leq n_i$ , and for any $i\in [m]\setminus [t]$ , we have that $|V(H^{\prime }_i)|=n_i$ , and $|\bigcup _{i=1}^mV(H^\prime _i)|\leq 5\gamma n$ . Also, for every vertex pair $(u, v)$ of $D-\bigcup _{i=1}^m H^\prime _i$ , there exists an absorber in $H^\prime _i$ ( $i\in [t]$ ) for it. Let $D^{0}=D-\bigcup _{i=1}^m H_{i}^{\prime }$ , and then $\delta ^0(D^0)\geq (1/2-5\gamma )n$ . Then by Lemma 3.6, we know that $D^{0}$ contains a Hamiltonian path, and then we divide this Hamiltonian path into $t$ disjoint paths $P_1, \ldots , P_t$ , of orders $n_1-V(H^{\prime }_1), \ldots , n_t-V(H^{\prime }_t)$ , respectively. Without loss of generality, for any $j\in [t]$ , we assume that $P_j=c_j\cdots d_j$ . By Lemma 3.5(iii), we get that for every $j\in [t]$ , the subdigraph $H^{\prime }_j$ contains an absorber for $(c_j, d_j)$ , and so $H^\prime _j\cup P_j$ is an $H$ -subdivision of order $n_j$ with the same branch-vertices as $H^{\prime }_j$ . So far, we have obtained $m$ disjoint $H$ -subdivisions, of order $n_1, \ldots , n_m$ , respectively. Hence, this suggests that Theorem 1.5 holds for the non-extremal case when $D$ is $\varepsilon ^{\prime }$ -stable.

4.1 Extremal cases and properties

We now define the following three extremal cases that will occur when $D$ satisfies the extremal condition with parameter $\varepsilon$ (EC( $\varepsilon$ )).

(1) Extremal Case $\mathbf{1}$ with parameter $\mathbf{\varepsilon }$ (EC1( $\mathbf{\varepsilon }$ )): We can partition $V(D)$ into three disjoint vertex sets $W_1$ , $W_2$ and $W_3$ , such that for every $i\in [2]$ , $|W_i|=(1/2-\varepsilon )n\pm \sqrt {10\varepsilon }|W_i|$ , and $|W_3|\leq 2\sqrt {10\varepsilon }\cdot \max \{|W_1|, |W_2|\}$ , and the following properties hold (see Fig. 1 $(a)$ ).

$(1.1)$ For each $i\in [2]$ , there exists a subset $W_i^{\prime }$ in $W_i$ with $|W_i^{\prime }|\leq 10\sqrt {\varepsilon }|W_i|$ such that for every vertex $w$ in $W_i\setminus W_i^\prime$ , $\delta ^0_{W_i}(w)\geq (1-10\sqrt {\varepsilon })|W_i|$ , and for every vertex $w$ in $W_i^\prime$ , $\delta ^0_{W_i}(w)\geq \varepsilon ^{1/3}|W_i|/2$ . We also say that $D[W_i]$ is $\varepsilon$ -almost complete, for each $i\in [2]$ .

$(1.2)$ For any vertex $w\in W_3$ , we have that either $d^+_{W_1}(w), d^-_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ , or $d^-_{W_1}(w), d^+_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ , and $\delta ^0_{W_i}(w)\leq \varepsilon ^{1/3}n/2$ for each $i\in [2]$ .

Figure 1.

The extremal cases $1$ - $3$ . Note that in this figure, a thick arrow pointing between two vertex sets indicates that the induced digraph by them is $\varepsilon$ -almost one-way complete, and the grey shading indicates that the digraph induced by this vertex set is $\varepsilon$ -almost complete. Also, the blue shaded areas indicate the exceptional vertices in the corresponding vertex sets.

Figure 1. Long description

A diagram illustrating extremal cases of digraphs. Panel A: The extremal case 1 (EC1). This panel shows three vertex sets labeled W1, W2, and W3. Thick arrows point between W1 and W3, and between W2 and W3, indicating that the induced digraph by these sets is almost one-way complete. The grey shading indicates that the digraph induced by W3 is almost complete, and the blue shaded areas indicate the exceptional vertices in the corresponding vertex sets. Panel B: The extremal case 2 (EC2). This panel shows three vertex sets labeled W1, W2, and W3. Thick arrows point between W1 and W3, and between W2 and W3, indicating that the induced digraph by these sets is almost one-way complete. The grey shading indicates that the digraph induced by W3 is almost complete, and the blue shaded areas indicate the exceptional vertices in the corresponding vertex sets. Panel C: The extremal case 3 (EC3). This panel shows four vertex sets labeled W1, W2, W3, and W4, with an additional vertex set W5 in the center. Thick arrows point between all pairs of vertex sets, indicating that the induced digraph by these sets is almost one-way complete. The grey shading indicates that the digraph induced by W3 and W4 is almost complete, and the blue shaded areas indicate the exceptional vertices in the corresponding vertex sets.

(2) Extremal Case $\mathbf{2}$ with parameter $\mathbf{\varepsilon }$ (EC2( $\mathbf{\varepsilon }$ )): We can partition $V(D)$ into three disjoint vertex sets $W_1$ , $W_2$ and $W_3$ such that for every $i\in [2]$ , $|W_i|=(1/2-\varepsilon )n\pm \sqrt {10\varepsilon }|W_i|$ , and $|W_3|\leq 2\sqrt {10\varepsilon }\cdot \max \{|W_1|, |W_2|\}$ , and the following hold (see Fig. 1 $(b)$ ).

$(2.1)$ For every $i\in [2]$ , apart from at most $10\sqrt {10\varepsilon }|W_i|$ exceptional vertices, all vertices in $W_i$ have bidirectional semi-degrees at least $(1-10\sqrt {\varepsilon })|W_{3-i}|$ in $W_{3-i}$ , and the semi-degrees of these exceptional vertices are at least $\varepsilon ^{1/3}|W_{3-i}|/8$ in $W_{3-i}$ . In this case, we also call $(W_1, W_2)$ to be a $\varepsilon$ -almost complete bipartite digraph.

$(2.2)$ For every vertex $w\in W_3$ , we have that either $d^+_{W_1}(w), d^-_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ , or $d^-_{W_1}(w), d^+_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ , and $\delta ^0_{W_i}(w)\leq 2\varepsilon ^{1/3}n$ for each $i\in [2]$ .

(3) Extremal Case $\mathbf{3}$ with parameters $\mathbf{\varepsilon }$ and $\mathbf{\varepsilon _1}$ (EC3( $\mathbf{\varepsilon }$ , $\mathbf{\varepsilon _1}$ )): We can partition $V(D)$ into five disjoint vertex sets $W_1, W_2, W_3$ , $W_4$ and $W_5$ in $D$ with $|W_5|\leq 4\sqrt {10\varepsilon }n$ , $\varepsilon ^{1/3}n-\sqrt {10\varepsilon }n\lt |W_1|, |W_3|\lt (1/2-3\varepsilon _1/4)n+\sqrt {10\varepsilon }n$ and $\varepsilon ^{1/3}n-\sqrt {10\varepsilon }n\lt |W_2|, |W_4|\lt (1/2-\varepsilon _1/4)n+\sqrt {10\varepsilon }n$ such that $|W_1|\approx |W_3|$ and $|W_2|\approx |W_4|$ . Furthermore, the following statements hold (see Fig. 1 $(c)$ ).

$(3.1)$ For each $i\in \{1, 3\}$ , apart from at most $10\sqrt {\varepsilon }|W_i|$ exceptional vertices, all vertices have the semi-degrees in $W_i$ at least $(1-10\sqrt {\varepsilon })|W_i|$ , and the semi-degrees of these exceptional vertices in $W_i$ are at least $\varepsilon ^{1/3}|W_i|/2$ .

$(3.2)$ For $\{i, j\}=\{2, 4\}$ , in $W_i$ , apart from at most $10\sqrt {10\varepsilon }|W_i|$ exceptional vertices, all vertices in $W_i$ have bidirectional semi-degrees at least $(1-10\sqrt {\varepsilon })|W_j|$ in $W_j$ , and the semi-degrees of these exceptional vertices are at least $\varepsilon ^{1/3}|W_j|/8$ in $W_j$ . For the vertex set $W_j$ , we can get a similar conclusion by swapping all $i$ and $j$ above, respectively.

$(3.3)$ Without loss of generality, for any $i\in [2]$ , we assume that $|W_i|\geq |W_{2+i}|$ . Then for every vertex $w$ in $W_5$ and any pair $\{j_1, j_2\}\in \{\{1, 3\}, \{2, 4\}\}$ , it satisfies either $d_{W_{j_1}}^+(w), d_{W_{j_2}}^-(w)\geq (1-\varepsilon ^{1/3})|W_{j_1}|$ or $d_{W_{j_1}}^-(w), d_{W_{j_2}}^+(w)\geq (1-\varepsilon ^{1/3})|W_{j_1}|$ , and $\delta ^0_{W_j}(w)\leq \varepsilon ^{1/3}n/2$ for any $j\in \{1, 3\}$ , and $\delta ^0_{W_j}(w)\leq 2\varepsilon ^{1/3}n$ with $j\in \{2, 4\}$ .

$(3.4)$ For $i\in [4]$ , we have that $e^+(W_i, W_{i+1})\geq |W_i|\cdot |W_{i+1}|-\varepsilon ^{\prime } n^2/2$ , where the subscript of $W_{i+1}$ takes the remainder of modulo $4$ for $i=4$ . In particular, in this case we also say that $(W_i, W_{i+1})$ is $\varepsilon ^{\prime }$ -almost one-way complete corresponding to the vertex sets $W_i$ and $W_{i+1}$ .

Based on the extremal condition (EC( $\varepsilon$ )) and the definitions of EC1( $\varepsilon$ ), EC2( $\varepsilon$ ) and EC3( $\varepsilon , \varepsilon _1$ ), we can use traditional structural analysis methods to effectively demonstrate the following conclusion. Since its proof strategy essentially follows from that of Lemma $3.14$ in [Reference Cheng, Wang and Yan5], it is deferred to Appendix A.

Furthermore, we establish the following lemmas, which demonstrate how to properly handle the exceptional vertices in each extremal configuration of $D$ and will be frequently applied in the proofs of the main theorems. A set $\mathcal{P}$ is said to pass through a vertex $u$ if there exists an element in $\mathcal{P}$ that contains $u$ . If this holds for every vertex in a set $U$ , then $\mathcal{P}$ is said to pass through $U$ . We say a path $P$ is of the form $W_1W_2\cdots W_k$ if $P=w_1w_2\cdots w_k$ , where $w_i\in W_i$ for each $i\in [k]$ .

Proof. We define $W_{3, 1}$ (resp., $W_{3, 2}$ ) to be the set of vertices $w$ in $W_3$ satisfying that $d^-_{W_1}(w), d^+_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ (resp., $d^+_{W_1}(w), d^-_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ ). If $|W_{3, 1}|=|W_{3, 2}|$ , then for any $u\in W_{3, 1}$ and any $v\in W_{3, 2}$ , by the definitions of $W_{3, 1}$ and $W_{3, 2}$ , we have that

\begin{align*} \begin{split} &|N^-_{W_1}(u)\cap N^+_{W_1}(v)|\geq (1-2\varepsilon ^{1/3})n-|W_1|\gt n/3\quad \mbox{and}\\[3pt] &|N^+_{W_2}(u)\cap N^-_{W_2}(v)|\geq (1-2\varepsilon ^{1/3})n-|W_2|\gt n/3. \end{split} \end{align*}

This implies that there exist many (more than $|W_{3, 1}|$ ) disjoint paths $P$ with the form $W_2vW_1uW_2$ , and many (more than $|W_{3, 1}|$ ) disjoint paths $P^{\prime }$ of the form $W_1uW_2vW_1$ . Greedily, we can get that a family $\mathcal{P}$ of disjoint paths that cover all vertices of $W_3$ and each path in $\mathcal{P}$ is a $W_1$ -path or a $W_2$ -path, as requested.

So in the following, we consider the case of $|W_{3, 1}|\neq |W_{3, 2}|$ . Without loss of generality, suppose that $|W_{3, 1}|\gt |W_{3, 2}|$ and let $r=|W_{3, 1}|-|W_{3, 2}|$ . We denote by $M_1$ (resp., $M_2$ ) to be a set of disjoint arcs from $W_{3, 1}$ to $W_1$ (resp., from $W_{2}$ to $W_{3, 1}$ ), with $M_1$ and $M_2$ being disjoint from each other. We further choose each $M_i$ ( $i\in [2]$ ) to be maximal. Set $M=M_1\cup M_2$ , and for each $i\in [2]$ , define $W_{i}^{\prime }=W_{i}\setminus V(M)$ and $W_{3, 1}^{\prime }=W_{3, 1}\setminus V(M)$ . We now consider two subcases.

Case 1: $|M|\geq r$ . In this case, since for any $w\in W_{3, 1}$ , we have $d^-_{W_1}(w), d^+_{W_2}(w)\gt (1/2-\varepsilon ^{1/3})n$ , there are $r$ disjoint $W_1$ -paths and $W_2$ -paths of the forms $W_1M_1$ and $M_2W_2$ . Clearly, $|W_{3, 1}|-r=|W_{3, 2}|$ . Then for all remaining vertices $u$ in $W_{3, 1}$ and $v$ in $W_{3, 2}$ , similar to the previous paragraph and by the definitions of $W_{3, 1}$ and $W_{3, 2}$ , there are $|W_{3, 2}|$ disjoint $W_2$ -paths (or $W_1$ -paths) of form $W_2^{\prime } vW_1^\prime uW_2^\prime$ (or $W_1^\prime uW_2^\prime vW_1^\prime$ ), covering all remaining vertices in $W_{3, 1}$ and all vertices in $W_{3, 2}$ , as desired.