4.1. Digraphs with large dichromatic number and no large strong minor

Given digraphs H, G, D, let $\Delta(H, G, D)$ be the digraph obtained by taking vertex-disjoint copies of H, G, and D, adding all possible undirected edges with at most one endpoint in each of V(H), V(G), and V(D), and orienting the new edges so that $H \rightarrow G$ , $G\rightarrow D$ , and $D \rightarrow H$ .

Construction 1. Let $S_1 = K_1$ (i.e. the single vertex complete digraph with no edges). For $r \ge 2$ we set $S_r = \Delta(K_1, S_{r-1}, S_{r-1})$ . We illustrate this construction in Figure 1.

Figure 1.

The tournament $S_r.$

We remark that this construction has appeared before in [Reference Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott, Seymour and Thomassé2]. It is not difficult to check by induction that $\chi(S_r) = r$ for all $r \ge 1$ . The following shows that, in general, dichromatic number r is not sufficient to guarantee a strong $\overrightarrow{K}_{\!\!r}$ minor.

Proof. As mentioned, $\chi(S_r) = r$ is easy to verify by induction on r. We turn to determining ${\rm sm}(S_r)$ . Note that $S_2$ is simply a directed triangle and so clearly ${\rm sm}(S_2) = 1$ . Let $r \ge 3$ and suppose the result holds for smaller values. Since $S_r = \Delta(K_1, S_{r-1}, S_{r-1})$ , let us write A and B for the two copies of $S_{r-1}$ , and v for the copy of $K_1$ . Clearly, at most one branch set from any strong minor in $S_r$ contains v. If $X \subseteq V(S_r)$ is a strongly connected subset that does not contain v, then X cannot contain vertices from both A and B (since $A \rightarrow B$ ). Similarly, there cannot be one branch set contained in A and another contained in B. Since we can potentially add a new branch set in $S_r$ containing v, we have

\begin{equation*} {\rm sm}(S_r) \le {\rm sm}(S_{r-1}) + 1 \le r - 1,\end{equation*}

as claimed.

Construction 2. Let $G_1 = K_1$ and suppose $G_r$ has been constructed for some $r \ge 1$ . To form $G_{r+1}$ , consider first a transitive tournament $T_{r+1}$ on $r+1$ vertices. For each directed edge e of $T_{r+1}$ add pairwise disjoint copies of $G_r$ , denoted by $G^e_r$ , such that $V(G_r^e) \cap V(T_{r+1}) = \varnothing$ for all e. Finally, for each directed edge $e = vw$ in $T_{r+1}$ and each vertex $u \in V(G_r^e)$ create a directed triangle uvw.

Proof. Note that $G_2$ is a directed triangle, so we have $\chi(G_2) = 2$ and ${\rm sm}(G_2) = 1$ . So suppose $r \ge 3$ and the result holds for smaller values. Since each copy of $G_{r-1}$ in $G_r$ can be $(r-1)$ -coloured, we can r-colour $G_r$ using one extra colour for the transitive tournament. On the other hand, we cannot $(r-1)$ -colour $G_r$ : assume there is an $(r-1)$ -colouring of $G_r$ , then some two vertices $x, y \in V(T_r)$ receive the same colour, say 1. Let $e = xy$ be the corresponding edge in $T_r$ . As $\chi(G_{r-1}^e) = r - 1$ , the colour 1 must appear in $G_{r-1}^e$ , and so we obtain a directed triangle in colour 1, a contradiction.

Next, we shall show that ${\rm sm}(G_r) \leq r - 1$ . Let $t={\rm sm}(G_r)$ . Consider a strong $\overrightarrow{K}_t$ minor in $G_r$ with branch sets $B_1, \ldots, B_t$ . Since $T_r$ is not strongly connected, $B_i \not\subseteq V(T_r)$ for each $i=1, \ldots, t$ . Observe also that if for some edge $e=xy$ of $T_r$ , $B_i\cap V(G_{r-1}^e)\neq \emptyset$ and $B_i\setminus V(G_{r-1}^e)\neq \emptyset$ , then $B_i$ contains both x and y; otherwise, $B_i$ does not induce a strongly connected digraph. There are two cases to consider.

Case 1. There is $i \in [t]$ such that $B_i \subseteq V(G_{r-1}^e)$ for some edge $e=xy$ of $T_r$ .

Without loss of generality, assume $i =t$ . Let $V'=V(G_{r-1}^e)$ . Then any other $B_j$ , $j=1, \ldots, t-1$ should either be contained in V ^′ or contain x or y. If all $B_i$ ^′s are contained in V ^′, then by induction $t\leq r-2$ . Thus, we can assume that there is $j\in \{1, \ldots, t-1\}$ such that $B_j$ contains x or y. If $B_j$ intersects V ^′, we have that $B_j$ contains both x and y by an observation before the statement of the case. If $B_j$ does not contain vertices from V ^′, it also must contain both x and y, otherwise the edges between $B_t$ and $B_j$ go in one direction only. Since the $B_i$ ^′s are pairwise disjoint, there is exactly one such index j, such that $B_j$ is not contained in V ^′. The number of branch sets from $B_1, \ldots, B_t$ that are contained in V ^′ is by induction at most $r-2$ . Thus, ${\rm sm}(G_r)=t \leq r-2+1 = r-1$ .

Case 2. For each branch set $B_i$ , there exists an edge e of $T_r$ such that $B_i$ contains both vertices of e.

Since the $B_i$ ^′s are pairwise disjoint, the respective edges e must also be pairwise disjoint. Since $T_r$ has at most $r/2\leq r-1$ pairwise disjoint edges, $t\leq r-1$ . This completes the second case, and thus the proof.

4.2. Digraphs with large out-degree and no large strong minor

Here we show that large out-degree is not sufficient to guarantee strong $\overrightarrow{K}_{\!\!r}$ minors in general digraphs, and thus prove Theorem 1.4. To this end, we need Thomassen’s [Reference Thomassen23] construction of digraphs with large out-degree and no even cycle. The construction proceeds as follows.

Construction 3. Let $D_1$ be a directed triangle. Suppose $D_k$ is defined by induction. Now, add pairwise disjoint sets $A_x \cup \{x'\}$ where $|A_x| = k + 1$ , for every vertex $x \in V(D_k)$ , all of them disjoint from $V(D_k)$ . We then add all directed edges between $A_x$ and $N_{D_k}^+(x) \cup \{x\}$ such that $A_x \rightarrow \{x\} \cup N_{D_k}^+(x)$ , and $x \rightarrow x'$ . Finally, add all edges from x^′ to $A_x$ , and denote by $D_{k+1}$ the resulting digraph. We illustrate this construction in Figure 2.

Figure 2.

The digraph $D_k$ for $k=1, 2$ and sketch for general k.

Then $D_{k}$ clearly has minimum out-degree k, and one can check that it contains no even directed cycle (in particular, it contains no pair of vertices x, y with $xy, yx \in E(D_{k+1})$ ). The following asserts that $D_k$ does not contain large strong clique minors. In particular, large out-degree alone is not sufficient to guarantee strong minors in digraphs.

Proof. We proceed by induction on k. This is clearly true for $k = 1$ , so suppose $k \ge 2$ and the result holds for smaller values of k. Suppose, by way of contradiction, that $D_{k+1}$ contains a strong $\overrightarrow{K}_3$ minor with branch sets U, W, X. Since $D_k$ contains no strong $\overrightarrow{K}_3$ minor, it must be the case that at least one of these branch sets intersects $A_x \cup \{x'\}$ for some $x \in V(D_k)$ . So suppose U intersects $A_x \cup \{x'\}$ . We claim that $x \in U$ .

Indeed, first suppose that $x' \in U$ . Since $N^-(x') = \{x\}$ , any nontrivial directed path to x ^′ passes through x. As D[U] is strongly connected, we either have $x \in U$ or $U = \{x'\}$ . The latter cannot hold, since otherwise we must have both $x\in X$ and $x \in W$ , a contradiction. Thus, we have $x \in U$ .

Now suppose that $y \in U$ for some $y \in A_x$ . Then since $N^-(y) = \{x'\}$ , any nontrivial directed path to y includes x ^′, so either $x' \in U$ or $U = \{y\}$ . In the latter case, we must have both $x' \in X $ and $x' \in W$ , a contradiction. In the former case, we have $x \in U$ , by the above argument.

In any case, $x\in U$ as claimed. But then $U' = U\cap V(D_k) $ induces a strongly connected subdigraph in $D_k$ . Indeed, if $U' = \{x\}$ , then it is trivially strongly connected in $D_k$ . Otherwise, let $u, v \in U'$ be distinct vertices. Then any path from u to v that uses vertices not in $D_k$ , say from $A_{x} \cup \{x'\}$ , passes through x and eventually an out-neighbour z of x. So there is a path from u to v contained in U’, obtained by going from x directly to z and continuing outside of $A_x \cup \{x'\}$ . Similarly, we have that $W' = W\cap V(D_k) $ and $X' = X\cap V(D_k) $ induce strongly connected subdigraphs in $D_k$ .

Since U, W, and X are pairwise disjoint, then for any x at most one of these three sets intersects $A_x \cup \{x'\}$ . Since there are no edges between $A_x \cup \{x'\}$ and $A_y \cup \{y'\}$ for distinct x and y, all edges between U, W, and X are the edges between U’, W’, and x ^′. Thus U’, W’, and x ^′ form branch sets of a strong $\overrightarrow{K}_3$ minor in $D_k$ , a contradiction.

5.1. Large dichromatic number in tournaments

The aim of this section is to prove Theorem 1.2. Before doing so, however, we shall prove the following warm-up result, which shows that dichromatic number linear in r is sufficient to guarantee strong $\overrightarrow{K}_{\!\!r}$ minors in tournaments.

Proof. We proceed by induction on r. Clearly, this is true for $r = 1$ , so we may assume $r \ge 2$ and the result holds for smaller values of r. Suppose T is a tournament with $\chi(T) \ge 3r$ . We may assume T is strongly connected; otherwise, by Lemma 3.2, we can pass to a strongly connected component with dichromatic number at least 3r. Let $A \subset V(T)$ be a largest transitive subset with source s and sink t. Since T is strongly connected, there exists a directed path in T from t to s. Pick a shortest directed path P from t to s. Note that $\chi(T[V(P)]) \le 2$ : by the minimality of P, all edges between vertices of P that have distance at least 2 on the path are oriented backwards. It follows that vertices at odd/even distances from the initial vertex produce a 2-colouring of P. Then $\chi(T[A \cup V(P)]) \le 3$ . Let $T' = T - (A \cup V(P))$ . It follows that $\chi(T') \ge 3r - 3 = 3(r-1)$ . By induction, we have that T ^′ contains a strong $\overrightarrow{K}_{r-1}$ minor.

Observe that the maximality of A implies that for every vertex $v \in V(T) \setminus A$ , v has at least one out-neighbour and at least one in-neighbour in A. In particular, for each branch set of our strong $\overrightarrow{K}_{r-1}$ minor in T ^′, there are edges in both directions between A and this branch set. Finally, note that $T[A \cup V(P)]$ is strongly connected, so $A \cup V(P)$ can be taken as the rth branch set in a strong $\overrightarrow{K}_{\!\!r}$ minor in T, completing the induction and the proof.

The proof of Proposition 5.1 follows by first considering a maximal transitive set, ensuring that this set is in and out ‘dominating’, and then making this set strongly connected by attaching a shortest path. Using this naive approach, we can only guarantee the resulting set has dichromatic number at most 3. We would like to reduce ‘3’ to ‘2’, and thus in order to prove Theorem 1.2, we must work a little harder. The following lemma, which may be viewed as the heart of the proof of Theorem 1.2, shows that one can find strongly connected dominating sets of dichromatic number 2 in any strongly connected tournament. This is clearly tight on the dichromatic number and it is a result of independent interest.

Before embarking on the proof, let us introduce some useful terminology. Let D be a digraph, let $S \subseteq V(D)$ , and let $X \subseteq V(D) \setminus S$ . We say that S out-dominates (in-dominates, resp.) X if every $x \in X$ has at least one in-neighbour (out-neighbour, resp.) in S. If $X = V(D) \setminus S$ , we say that S is out(in)-dominating. If S is both out-dominating and in-dominating, we shall say that S is dominating (or, that it is a dominating set).

Proof. We illustrate the proof in Figure 3. Let x be a vertex in T with maximum out-degree in T. Let S(x) be a largest possible transitive subtournament with sink x. Denote by y the source of S(x). Observe that since S(x) is maximum-sized, it must be out-dominating: for all $v \in V(T) \setminus S(x)$ there is $u \in S(x)$ such that $u \rightarrow v$ . Moreover, as x has maximum out-degree in T, there exists a vertex $w^* \in V(T) \setminus S(x)$ such that $x \rightarrow w^*$ and $w^* \rightarrow y$ , otherwise y would have a larger out-degree than x.

Figure 3.

The proof of Lemma 5.2. The direction of $ww^*$ is not important for the proof.

Now, let $F=\bigcap_{s \in S(x)} N^{+}(s)$ . The set F consists of the vertices that are not in-dominated by S(x). If $F = \varnothing$ , then we are done, since then we may take $R = S(x) \cup \{w^*\}$ . So we may assume that $F \neq \varnothing$ . Let $F^+ \subseteq F$ be the set of vertices in F that have an out-neighbour in $V(T) \setminus F$ . Since T is strongly connected, it follows that $F^+ \neq \varnothing$ . We need to find a set (hopefully of small dichromatic number) that in-dominates the vertices in F. First, we prove the following claim showing that we may partition F in a useful way.

1. (1) for every $u \in F_{i+1}$ there is $z \in F_{i}$ such that $u \rightarrow z$ , and

2. (2) for every j, $j>i+1$ , $F_i \rightarrow F_j$ .

Proof. Let $F_1 = F^+$ . Suppose $F_1, \ldots, F_i$ have been constructed for some $i \ge 1$ . Let $Y = F \setminus (\bigcup_{j \in [i]} F_j)$ . If $Y = \varnothing$ , then stop with $k\;:\!=\;i$ . Otherwise, let

\begin{equation*} F_{i+1} = \left(\bigcup_{u \in F_i}N^-(u)\right)\cap Y.\end{equation*}

Note that $F_{i+1}$ is non-empty due to the strong-connectivity of T. Indeed, if $F_{i+1} = \varnothing$ , then $F_i \rightarrow Y$ and since $Y \cap F_1 = \varnothing$ , no vertex of Y has an out-neighbour in $V(T) \setminus F$ . Thus, there is no directed path from a vertex in Y to a vertex in $F_1 = F^+$ , a contradiction to the strong-connectivity assumption.

Also, note that

\begin{equation*} \bigcup_{j \in [i]}F_j \rightarrow Y\setminus F_{i+1}.\end{equation*}

By construction, every vertex in $F_{i+1}$ has at least one out-neighbour in $F_i$ . This completes the proof of the claim.

Let $S_k$ be a largest transitive set contained in $T[F_k]$ . If $F_{k-1}$ exists (i.e. $k \ge 2$ ), let $S = S_k \cup S_{k-1}$ , where $S_{k-1} \subseteq F_{k-1}$ is as large as possible such that S is transitive, and all vertices of $S_{k-1}$ lie after the vertices in $S_k$ in the transitive order. If $k=1$ , let $S=S_1$ . Let s denote the sink of S. In particular, either $s \in F_k$ or $s \in F_{k-1}$ . Intuitively, S in-dominates F (which we shall show later), and it remains to ‘connect’ S to S(x) to find a dominating set that is strongly connected.

To this end, consider a shortest directed path $P=s\ldots x_1$ contained in F from s to a vertex in $F_1$ ; such a path exists by Claim 1. Also, observe that since P is a shortest path in F to $F_1$ , it has exactly one vertex in each $F_i$ . Now, since $x_1 \in F_1 = F^+$ , by definition of $F^+$ we may choose an out-neighbour $w \in V(T) \setminus (F \cup S(x))$ of $x_1$ . It is possible that $w = w^*$ , but this only makes the proof simpler. So we assume that $w \neq w^*$ . Finally, let

\begin{equation*} R=S(x)\cup S \cup V(P)\cup W.\end{equation*}

The following sequence of claims shows that R has all of the desired properties (see Figure 3).

Proof. First, note that $T[S(x)\cup W]$ is strongly connected. Indeed, $T[S(x) \cup \{w^*\}]$ is strongly connected since $w^* \in N^-(y) \cap N^+(x)$ . As $w \notin F$ , it has an out-neighbour $v \in S(x)$ , and the maximality of S(x) implies that w has an in-neighbour $v' \in S(x)$ . It follows that T[R] is strongly connected, as claimed.

Proof. S(x) dominates $V(T) \setminus (S(x) \cup F)$ : the maximality of S(x) implies that it is out-dominating, and it additionally in-dominates $V(T) \setminus F$ (since F is exactly the set of vertices not in-dominated by S(x)). So it suffices to show that R in-dominates $F \setminus (S \cup V(P))$ . In particular, we claim that S in-dominates $F \setminus (S \cup V(P))$ . Indeed, by (2) of Claim 1 we have

\begin{equation*}\bigcup_{i \le k - 2} F_i \rightarrow S \cap F_k,\end{equation*}

so it suffices to show that S in-dominates $(F_k \cup F_{k-1)}) \setminus S$ . Recall that $S = S_k \cup S_{k-1}$ where $S_k$ is a largest transitive set in $F_k$ , and $S_{k-1}$ is a largest possible transitive extension of $S_k$ in $F_{k-1}$ such that all vertices of $S_{k-1}$ lie after $S_k$ in the transitive order. Thus, if there is some vertex $z \in (F_k \cup F_{k-1}) \setminus S$ such that $S \rightarrow z$ , we obtain a contradiction with our choice of S. It follows that S in-dominates $(F_k \cup F_{k-1}) \setminus S$ , as claimed.

Proof. We produce a 2-colouring of R that depends on the parity of k and also on whether s (the sink of S) is in $F_k$ or $F_{k-1}$ . We deal with the case when k is even first, and sketch the proof when k is odd, as the proof is nearly identical. Recall that as $P = s\ldots x_1$ is a shortest $s-F_1$ path in F, it has exactly one vertex in each $F_i$ (except for maybe $F_k$ ).

Case 1: k is even. First, suppose that $k=2$ . If $s \in F_2$ , then let one colour class be $S(x) \cup \{x_1\}$ and the other $S \cup W$ . Note that the latter set is transitive since $S \subseteq F_2$ and so sends no out-edges to $V(T) \setminus F$ . On the other hand, if $s \in F_1$ , then let one colour class be $S(x) \cup (S \cap F_1)$ and the other $(S \cap F_2) \cup W$ .

Now, suppose $k>2$ and $x_k \;:\!=\; s \in F_k$ . Write $P = x_kx_{k-1}\ldots x_1$ with $x_i \in F_i$ for all $i \in [k]$ . Let $P_{\text{odd}} = \{x_1, x_3, \ldots, x_{k-1}\}$ and $P_{\text{even}} = \{x_2, x_4, \ldots, x_k\}$ . Then we can let one colour class be $S(x) \cup P_{\text{odd}}$ and the other $S \cup P_{\text{even}} \cup W$ . Indeed, S(x) is transitive and $S(x) \rightarrow P_{\text{odd}}$ . Moreover, $T[P_{\text{odd}}]$ is transitive by (2) of Claim 1. Similarly, since $x_k = s \in F_k$ and $k > 2$ , we have $S \cup P_{\text{even}} \subseteq F \setminus F_1$ and so $W \rightarrow S \cup P_{\text{even}}$ . As before, $T[S \cup P_{\text{even}}]$ is transitive and clearly so is W.

Lastly, we consider the case when $x_{k-1} \;:\!=\; s \in F_{k-1}$ , that is, when $P=x_{k-1},\ldots, x_1$ let $P_{\text{even}} = \{x_2, \ldots, x_{k-2}\}$ and let $P_{\text{odd}}= V(P) \setminus P_{\text{even}}$ . In this case, we let one colour class be $S(x) \cup P_{\text{odd}} \cup (S \cap F_{k-1})$ and the other be $(S \cap F_k) \cup P_{\text{even}} \cup W$ . It is routine to check that this is indeed a 2-colouring using the same arguments as above.

Case 2: k is odd. If $k=1$ , let $S(x)\cup S$ be one colour class, and W the other. If $k >1$ , then an analogous argument as in the previous case yields a 2-colouring of R.

Hence, R satisfies all of the claimed properties. This completes the proof of the lemma.

We can now easily deduce Theorem 1.2.

Proof of Theorem 1.2. We have already established the second part of the statement in Proposition 4.1. It remains to prove the first part.

We proceed by induction on r. Clearly, the result holds for $r = 1$ , so we suppose $r \ge 2$ and the theorem holds for smaller values. Let T be a tournament with $\chi(T) \ge 2r$ , and, by Lemma 5.2, we may assume T is strongly connected. Lemma 5.2 grants a subset $R \subseteq V(T)$ such that T[R] is strongly connected, R is dominating in T, and $\chi(T[R]) = 2$ . Letting $T' = T - R$ , we see that $\chi(T') \ge 2r - 2 = 2(r-1)$ , and so by induction T ^′ contains a strong $\overrightarrow{K}_{r-1}$ minor. Taking R as the rth branch set yields a strong $\overrightarrow{K}_{\!\!r}$ minor in T.

Perhaps the correct constant in Theorem 1.2 should be ‘1’ instead of ‘2’ as indicated by the construction $S_r$ . In other words, it is possible that any tournament with dichromatic number at least $r + 1$ contains a strong $\overrightarrow{K}_{\!\!r}$ minor. We can prove this in the first nontrivial case:

Proof. Pick a directed triangle $C_1$ in T. Since $\chi(T) \ge 3$ , $T - C_1$ is non-empty. If there is a vertex $v \notin C_1$ that sends edges in both directions to $C_1$ , then we are done. Otherwise, $T-C_1$ can be partitioned into two sets $A_1$ and $B_1$ such that $A_1 \rightarrow C_1$ and $C_1 \rightarrow B_1$ . If there is an edge e from $B_1$ to $A_1$ , then we are done. Indeed, one branch set is the directed triangle formed from e and one vertex of $C_1$ , and the other branch set is just one of the remaining vertices of $C_1$ . So we may assume that $A_1 \rightarrow B_1$ . In this case, we either have $\chi(A_1) \ge 3$ or $\chi(B_1) \ge 3$ . Without loss of generality, $\chi(A_1) \ge 3$ , and so we pass to this subtournament and repeat the argument.

In this process, we obtain a sequence of non-empty sets strictly decreasing in size, so it must eventually terminate with a strong $\overrightarrow{K}_2$ minor.

5.2. Large out-degree in tournaments

In this section, we turn our attention to investigating the presence of strong minors in tournaments with a minimum out-degree condition. In particular, we prove Theorem 1.3. The strategy of our proof is as follows. First, we show that there is a constant C’ such that any tournament that is $C'r\sqrt{\log r}$ -strongly connected contains a strong $\overrightarrow{K}_{\!\!r}$ minor (see Lemma 5.8). Given a tournament T with $\delta^+(T) \ge Cr\sqrt{\log r}$ where $C \gg C'$ , we may assume that no subtournament of T is $C'r\sqrt{\log r}$ -strongly connected. This assumption together with the minimum out-degree condition allows us to iteratively construct a strong $\overrightarrow{K}_{\!\!r}$ minor in which every branch set is, in fact, a directed triangle. This last step is made precise in Lemmas 5.9 and 5.10.

Before proceeding, we need a few preliminary results. Given a positive integer k and a digraph D, we say that D is k-linked if $|V(D)| \ge 2k$ and for any two disjoint sets of vertices $\{x_1, \ldots , x_k\}$ and $\{y_1, \ldots, y_k\}$ of k vertices each, there are pairwise vertex-disjoint directed paths $P_1, \ldots , P_k$ such that $P_i$ has initial vertex $x_i$ and terminal vertex $y_i$ for every $i \in [k]$ . We shall use the following theorem of Pokrovskiy [Reference Pokrovskiy18], showing that large enough strong-connectivity guarantees linkedness in tournaments.

Recall that a weak minor has the same definition as a strong minor except that we only require that the branch sets induce connected (not necessarily strongly connected) subgraphs. As mentioned in the Introduction, Jagger [Reference Jagger11] investigated average degree conditions for finding weak minors in digraphs. In the context of tournaments, we need the following:

During the course of the proof of Theorem 1.3, we shall construct an auxiliary (undirected) graph and apply the following classical result:

Finally, we need one more preliminary result. We say that a subset $B \subset V(T)$ is K-nearly-regular if either $d^-_T(v) \le d^+_T(v) \le Kd^-_T(v)$ for every $v \in B$ , or $d^+_T(v) \le d^-_T(v) \le Kd^+_T(v)$ for every $v \in B$ . The following lemma appears in [Reference Girão, Popielarz and Snyder5]. We reproduce the proof here for convenience.

Proof. Let $|T| = n$ ; we may assume $n \ge 20$ , otherwise the result is trivial. Let $R \subset V(T)$ be the set of vertices for which either the ratio between the out-degree and in-degree or vice-versa is between 1 and 4. If $|R|\geq n/10$ , then we are done, as we may pass to a subset $A \subset R$ of at least half the size of R that is 4-nearly-regular. If $|R| < n/10$ , then let $T'=T - R$ , so that $|T'| > 9n/10$ . Let $T'_1$ be the set of vertices $v \in V(T')$ for which $d_T^+(v) > 4d_T^-(v)$ and $T'_2$ be those vertices $v \in V(T')$ for which $d_T^-(v) > 4d_T^+(v)$ . Suppose without loss of generality that $|T'_1|\geq |T'_2|$ , so that $|T'_1|\geq \lceil{9n/20}\rceil$ . Since each tournament on t vertices has a vertex of in-degree $\ge \lceil (t-1)/2\rceil$ , this implies that there is a vertex u in $T'_1$ which has in-degree inside $T'_1$ at least $(\lceil{9n/20}\rceil - 1)/2$ . However,

\begin{equation*} d_T^-(u) < \frac{1}{4}d_T^+(u) < \frac{1}{4}(n - d_T^-(u)),\end{equation*}

implying that $d_T^-(u) < n/5$ . Thus, we obtain

\begin{equation*} (\lceil{9n/20}\rceil - 1)/2 \le d_T^-(u) < n/5,\end{equation*}

which yields a contradiction for $n \ge 20$ .

Finally, let $R \subseteq V(T)$ be 4-nearly-regular, and assume without loss of generality that $d^-_T(u) \le d^+_T(u) \le 4d^-_T(u)$ for all $u \in R$ . If for some $v \in R$ we have $d^-_T(v) < n/6$ , then $d^+_T(v) < 2n/3$ , and so $n - 1 = d^+_T(u) + d^-_T(u) < 5n/6$ , a contradiction since $n \ge 20$ .

With these preliminaries in place, we shall prove our first lemma, guaranteeing strong $\overrightarrow{K}_{\!\!r}$ minors in $C'r\sqrt{\log r}$ -strongly connected tournaments. The strategy is to first embed a weak $\overrightarrow{K}_{\!\!r}$ minor in a ‘nice’ portion of the tournament (using Theorem 5.5), and then make each branch set strongly connected by linking appropriate pairs of vertices.

Proof. Put $C_0 = \max\{C, 24\}$ where C is given by Theorem 5.5. Let $C' = 40C_0$ , and suppose T is a tournament that is $C'r\sqrt{\log r}$ -strongly connected. By Lemma 5.7, we can find a subset $S\subset V(T)$ of size at least $\lfloor{|T|/20}\rfloor \ge C_0r\sqrt{\log r}$ such that all vertices of S have in- and out-degree at least $|T|/6$ . Take a subset $S'\subset S$ of size exactly $C_0r\sqrt{\log r}$ (ignoring floors/ceilings) and let $T'=T - S'$ . Find a weak $\overrightarrow{K}_{\!\!r}$ minor in S ^′ with branch sets $B_1, \ldots, B_r$ , using Theorem 5.5.

Since T ^′ is still $19C_0r\sqrt{\log r}$ -strongly connected, by Theorem 5.4, T^′ is $(19C_0/452)r\sqrt{\log r}$ -linked. Hence, T ^′ is r-linked by our choice of $C_0$ . We now construct a strong $\overrightarrow{K}_{\!\!r}$ minor as follows. For each $i \in [r]$ , if $T[B_i]$ is already strongly connected, then we take $B_i$ as a branch set. Otherwise, $B_i$ decomposes into strongly connected components $X^i_1, \ldots, X^i_t$ for some $t \ge 2$ , such that $X^i_p \rightarrow X^i_q$ for all $1 \le p < q \le t$ . Let $s_i^1$ be any vertex in $X^i_1$ and let $s_i^2$ be any vertex of $X^i_t$ .

Now, every vertex in S ^′ has many in and out-neighbours in T ^′. More precisely, every vertex in S ^′ has at least

\begin{equation*} |T|/6 - |S'| \ge \frac{20C_0r\sqrt{\log r}}{6} - C_0r\sqrt{\log r} > C_0r\sqrt{\log r},\end{equation*}

in-neighbours and out-neighbours in T ^′. Thus, for each $s_i^1$ we may choose an in-neighbour $u_i^1 \in V(T')$ , and for each $s_i^2$ we may choose an out-neighbour $u_i^2 \in V(T')$ , such that the vertices $u_i^j$ are all pairwise distinct. In this way, we have disjoint sets $X = \{u_1^1, \ldots, u_s^1\}$ and $Y = \{u_1^2, \ldots, u_s^2\}$ where $s \le r$ . Finally, use the fact that T ^′ is r-linked to find pairwise vertex-disjoint directed paths $P_i$ in T ^′ from $u_i^1$ to $u_i^2$ for each $i \in [s]$ . Clearly, $T[B_i \cup V(P_i)]$ is strongly connected for each $i \in [s]$ , and thus we have found a strong $\overrightarrow{K}_{\!\!r}$ minor in T.

Lemma 5.8 is tight up to the constant C, by considering a random tournament T on $cr\sqrt{\log r}$ vertices. As mentioned in the Introduction, following the argument of Bollobás, Catlin, and Erdös [Reference Bollobás, Catlin and Erdös3], w.h.p. it contains no strong $\overrightarrow{K}_{\!\!r}$ minor (in fact, it contains no r pairwise disjoint non-empty sets with edges in each direction between each pair of sets). Additionally, it is not hard to show that w.h.p. T is $(cr\sqrt{\log r})/10$ -strongly connected. This can be seen by noting that w.h.p. every two vertices have at least approximately $|T|/10$ directed paths of length 2 in each direction.

The following two lemmas allow us to find some structure in a tournament with large minimum out-degree, under the additional assumption that it is not highly strongly connected. We use the following notation in their formulations. If $\mathcal{H}$ is a family of subdigraphs of D, let $\bigcup \mathcal{H}$ denote the set $\bigcup_{H \in \mathcal{H}} V(H)$ .

Proof. Assume that T is not m-strongly connected and let R be a smallest cut-set of size at most $m-1$ . Observe that $R \neq \varnothing$ : if T itself is not strongly connected, then consider the source set X and sink set Y of T. Since $X \rightarrow Y$ , we must have $\delta^+(T[Y]) \ge d$ , contradicting the minimality of T.

Let A and B denote the source set and sink set of $T - R$ , respectively, and define

\begin{equation*} R' =\{x\in R\;:\;|N^+(x) \cap (B \cup R)| <d\}.\end{equation*}

The minimality of T implies that $R'\neq \varnothing$ : if $R' = \varnothing$ , then $\delta^+(T[B\cup R]) \ge d$ , a contradiction. Now, choose a maximum matching $M = \{w_1v_1, \ldots, w_tv_t\}$ from R ^′ to A and let $T' = T[(B\cup R)\setminus V(M)]$ and $S = M$ . We claim that T ^′ and S satisfy the required properties. Clearly, the first property is satisfied. To see the last property suppose that $x\in B\cup (R\setminus R')$ , then its degree is at least $d-t$ in T ^′. On the other hand, if $x\in R'\setminus V(M)$ , since we cannot extend the matching M, $N_{T}^{+}(x)\cap A\subset V(M)$ , which implies $d_{T'}^+(x)\geq d-|V(M)|=d-2t$ . To see the second property, consider a vertex $v_i$ . Then $v_i \rightarrow B$ , and so there are at most $|R|\leq m - 1$ vertices in $|T'|$ that are in-neighbours of $v_i$ . Similarly, consider a vertex $w_i$ . Since $w_i \in R'$ , by definition $|N^+(x) \cap (B \cup R)| < d$ . Thus, $w_i$ has at least $|T'| - d + 1$ in-neighbours in T ^′.

Our final lemma is obtained from iteratively applying Lemma 5.9 under the assumption that no subtournament is highly strongly connected.

Proof. We iteratively apply Lemma 5.9. Begin by removing vertices from T such that the remaining tournament $T_0$ is vertex-minimal with $\delta^+(T_0) \ge d$ . Then, since $T_0$ is not m-strongly connected by assumption, Lemma 5.9 implies that there is a positive integer $t_1 < m$ , a set of edges $S_1 = \{w^1_iv^1_i \;:\;i \in [t_1] \}$ , and a subtournament $F_1 \subseteq T_0$ such that

1. • $V(F_1) \cap (\bigcup S_1) = \varnothing$ ,

2. • $\delta^+(F_1) \ge d - 2t_1$ , and

3. • $|N^+(v_i^1) \cap F_1| \ge |F_1| - m $ and $|N^-(w_i^1) \cap F_1| \ge |F_1| - d$ for all $i \in [t_1]$ .

We proceed by applying Lemma 5.9 inside $F_1$ . Now assume we have already found subtournaments $F_1 \supset \cdots \supset F_k$ with $\delta^+(F_k) \ge d -2 \sum_{i=1}^k t_i$ , and disjoint sets of edges $S_1, \ldots, S_k$ of sizes $t_1, \ldots, t_k$ , such that for each $j \in [k]$ we have $|N^+(v_i^j) \cap F_k| \ge |F_k| - m $ and $|N^-(w_i^j) \cap F_k| \ge |F_k| - d$ for all $i \in [t_k]$ .

Assume that $\sum_{i=1}^k t_i < m$ . We first find a vertex-minimal subtournament $T_k$ of $F_k$ such that $\delta^+(T_k) \ge d -2\sum_{i=1}^k t_i$ . Since by assumption $T_k$ is not m-strongly connected, Lemma 5.9 implies that there is $t_{k+1} < m$ , a non-empty set of edges $S_{k+1} = \{w_i^{k+1}v_i^{k+1} \;:\;i \in [t_{k+1}]\}$ , and a subtournament $F_{k+1} \subseteq T_{k}$ such that

1. • $V(F_{k+1}) \cap (\bigcup S_{i}) = \varnothing$ for $i \in [k+1]$ ,

2. • $\delta^+(F_{k+1}) \ge \delta^+(T_k) - 2t_{k+1} \ge d - 2\sum_{i=1}^{k+1} t_i$ ,

3. • $|N^+(v_i^j) \cap F_{k+1}| \ge |F_{k+1}| - m$ and $|N^-(w_i^j) \cap F_{k+1}| \ge |F_{k+1}| - d$ for $j \in [k+1]$ and $i \in [t_j]$ .

We stop this process at a step $k_0$ when $\sum_{i=1}^{k_0} t_i \ge m$ , and let

\begin{equation*} S = \bigcup_{i=1}^{k_0} S_i \quad \text{ and } \quad F(S) = F_{k_0}. \end{equation*}

Then clearly properties (2) and (3) of the claim are satisfied, and we have a set S of at least m edges which are all disjoint from F(S). We just need to show that $|F(S)| \ge 2(d - 4m)$ . Since $\sum_{i=1}^{k_0-1}t_i < m$ and $t_{k_0} < m$ , we have that $\sum_{i=1}^{k_0} t_i < 2m$ , and so $\delta^+(F_{k_0}) \ge d - 4m$ . Thus,

\begin{equation*}|F(S)| = |F_{k_0}| \ge 2\delta^+(F_{k_0}) \ge 2(d - 4m),\end{equation*}

as claimed.

We are now in position to prove Theorem 1.3.

Proof of Theorem 1.3. As we already mentioned, the tightness can be seen by considering a random tournament on $\Omega(r\sqrt{\log r})$ vertices.

Now, let C ^′ be the constant given by Lemma 5.8 and let c be the constant given by Theorem 5.6. Put $C_0' = \max\{C', 62c\}$ and $C = 1600C_0'$ . Define $m = C'r\sqrt{\log r}$ and $d = Cr\sqrt{\log r}$ , and suppose T is a tournament with $\delta^+(T) \ge d$ . Note that $C\geq 1600C'$ . If T, or any subtournament of T, is m-strongly connected, then we are done by Lemma 5.8; so we may assume otherwise. In this situation, we may apply Lemma 5.10. Indeed, let S and F(S) be given as in Lemma 5.10, and let $N_i=N^{-}(w_i)\cap F(S)$ , $M_i=N^{+}(v_i)\cap F(S)$ , and $L_i=M_i\cap N_i$ . We first observe that for each $i \in [m]$

(5.1) \begin{equation} | L_i| \ge |F(S)| - d - m \ge d/2 - m \ge d/4,\end{equation}

using the fact that $|F(S)| \ge 2(d - 4m)$ . For every $i \in [m]$ choose a vertex $z_i$ from $L_i$ uniformly at random with replacement and let L denote the resulting random set of vertices. Note that $\Delta_i \;:\!=\;\{w_i,v_i,z_i\}$ forms a directed triangle. Let X denote the random variable recording the size of a largest subset of L in which all vertices are pairwise distinct. Further, let x ^′ count the number of pairs $\{z_i, z_j\}$ with $i \neq j$ and $z_i = z_j$ . We have that $\mathbb{P}(z_i = z_j) = |L_i \cap L_j|/ |L_i||L_j| \le 4/d$ using (5.1). It follows that $\mathbb{E}[X'] \le \binom{m}{2}\frac{4}{d} \le 2m^2/d$ , and hence

(5.2) \begin{equation} \mathbb{E}[X] \ge m - \mathbb{E}[X'] \ge m - 2m^2/d = (C'- 2C'^2/C) r\sqrt {\log r} \geq (C'/2) r\sqrt{\log r} = m/2,\end{equation}

since $C\geq 1600C'$ .

We say that a pair $\{\Delta_i, \Delta_j\}$ of directed triangles is good if there are edges between them in both directions; otherwise, we say this pair is bad. Observe that

\begin{align*}\mathbb{P}(\{\Delta_i, \Delta_j\} \text{ is bad }) &\le \mathbb{P}(z_j \notin N^{+}(v_i)\cap F(S) \text{ or } z_i \notin N^+(v_j)\cap F(S)) \\&\le \frac{m}{|L_j|} + \frac{m}{|L_i|} \le \frac{8m}{d} = \frac{8C'}{C} \leq \frac{1}{200},\end{align*}

using (5.1) and since $C \geq 1600C'$ . Hence, letting Y denote the random variable counting the number of bad pairs of directed triangles, we have that

(5.3) \begin{equation} \mathbb{E}[Y] \le \binom{m}{2}\frac{1}{200} \le m^2/400.\end{equation}

Combining (5.2) and (5.3), and using the Cauchy–Schwarz inequality, we have

\begin{equation*}\mathbb{E}\left[X^2 - 40Y - \frac{m^2}{9}\right] \ge \mathbb{E}[X]^2 - 40\mathbb{E}[Y] - \frac{m^2}{9}\ge \frac{m^2}{4} - \frac{m^2}{10} - \frac{m^2}{9} > 0.\end{equation*}

Accordingly, there is a choice of vertices from $\bigcup_{i =1}^m L_i$ such that $X^2 - 40Y - m^2/9 > 0$ . It follows that $X^2 \ge m^2/9$ , and so $X \ge m/3$ ; that is, there is a set U of at least $m/3$ vertices and they are all pairwise distinct. By possibly passing to a subset, let us assume $|U| = \lfloor{m/3}\rfloor$ . Moreover, we must have $40Y \le X^2 \le m^2$ , and so the number of bad pairs of triangles is at most $m^2/40$ .

Our final aim is to define a suitable auxiliary graph on our directed triangles and apply Theorem 5.6. Define a graph G in the following way: put $V(G) = \{\Delta_i\;:\;z_i \in U\}$ and join $\Delta_i$ to $\Delta_j$ if and only if the pair $\{\Delta_i, \Delta_j\}$ is good. By our above analysis, we have $|V(G)| = \lfloor{m/3}\rfloor$ , and there are at most $m^2/40$ non-edges in G. Thus, there are at least

\begin{equation*} \binom{\lfloor{m/3}\rfloor}{2} - m^2/40 \ge m^2/36 - m^2/40 \ge .0027 m^2,\end{equation*}

edges in G, and so the average degree is at least $.0162 m \ge .0162(62c r\sqrt{\log r}) > cr\sqrt{\log r}$ . Here we are using the fact that $m = C'r\sqrt{\log r}$ and $C' \ge 62c$ by definition. Applying Theorem 5.6 to G, we have that G contains a $K_r$ minor. It is easy to see that this $K_r$ minor corresponds to a strong $\overrightarrow{K}_{\!\!r}$ minor in the original tournament. This completes the proof of Theorem 1.3.