Blow-ups and extensions of trees in tournaments

Pierre Aboulker¹¹1DIENS, École normale supérieure, CNRS, PSL University, Paris, France. Research supported by the ANR project DAGDigDec (JCJC) ANR-21-CE48-0012 and by the group Casino/ENS Chair on Algorithmics and Machine Learning. Frédéric Havet²²2Université Côte d’Azur, CNRS, Inria, I3S, Sophia-Antipolis, France. Research supported by research grant DIGRAPHS ANR-19-CE48-0013. William Lochet³³3LIRMM, Université de Montpellier, CNRS, Montpellier, France. Research supported by research grant ELiT ANR-20-CE48-0008-01. Raul Lopes¹¹footnotemark: 1 ^,³³footnotemark: 3 Lucas Picasarri-Arrieta⁴⁴4National Institute of Informatics, Japan. Research supported by Japan Science and Technology Agency (JST) as part of Adopting Sustainable Partnerships for Innovative Research Ecosystem (ASPIRE), Grant Number JPMJAP2302. Clément Rambaud²²footnotemark: 2

Abstract

A class of acyclic digraphs $\mathcal{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in\mathcal{C}$ is contained in all tournaments of order $c\cdot|V(D)|$ . The class of all acyclic digraphs is not linearly avoidable, and Fox, He, and Widgerson recently showed that this is not even the case for acyclic digraphs with bounded maximum degree. On the positive side, Thomason and Häggkvist proved that the class of oriented trees is linearly unavoidable. In this work, we generalize this result to acyclic digraphs obtained from an oriented tree by adding at most $k$ vertices, and $k$ -blow-ups of oriented trees, for every fixed integer $k$ .

More precisely, we show that if $D$ is obtained from an oriented tree $F$ of order $n$ by adding $k$ universal vertices, then $D$ is contained in every tournament of order $2\cdot 3^{(k+1)(2k+1)}\cdot n$ ; and if $D$ is obtained from $F$ by replacing each vertex $u$ by an independent set $X_{u}$ of size $k$ and every arc $uv$ by all possible arcs from $X_{u}$ to $X_{v}$ , then $D$ is contained in every tournament of order $2^{10+18k}k\cdot n$ .

1 Introduction

A digraph is $p$ -unavoidable, for an integer $p$ , if it is contained in every tournament of order $p$ . For a digraph $D$ , the unavoidability of $D$ , denoted by $\operatorname{unvd}(D)$ , is the smallest integer $p$ such that $D$ is $p$ -unavoidable, if such a $p$ exists. It is easy and well-known that a digraph is $p$ -unavoidable for some integer $p$ if and only if it is acyclic. Indeed, every digraph containing a directed cycle is not contained in any transitive tournament, and so is not unavoidable. Moreover, as observed by Erdős and Moser [8], an immediate induction and Proposition 1 shows that the transitive tournament of order $n$ is $2^{n-1}$ -unavoidable and thus every acyclic digraph of order $n$ is $2^{n-1}$ -unavoidable.

Proposition 1.

Let $D$ be an acyclic digraph. For every source or sink $x$ of $D$ ,

\operatorname{unvd}(D)\leqslant 2\operatorname{unvd}(D-x).

This is somehow tight in the sense that any upper bound on the unavoidability of acyclic digraphs as a function of their order must be exponential. Indeed, considering a random tournament and using the First Moment Method, Erdős and Moser [8] established $\operatorname{unvd}(TT_{n})\geqslant 2^{(n-1)/2}$ . Since this seminal paper, only little progress has been made on the unavoidability of transitive tournaments. Using the Local Lemma, one can slightly improve on the lower bound and show that $\operatorname{unvd}(TT_{n})\geqslant 2^{(n+1)/2}$ when $n$ is large enough. The unavoidability of small transitive tournaments have been established. Clearly $\operatorname{unvd}(TT_{1})=1$ , $\operatorname{unvd}(TT_{2})=2$ , $\operatorname{unvd}(TT_{3})=4$ (because of the directed $3$ -cycle), and $\operatorname{unvd}(TT_{4})=8$ (because of the Paley tournament on $7$ vertices). Reid and Parker [22] showed $\operatorname{unvd}(TT_{5})=14$ , $\operatorname{unvd}(TT_{6})=28$ , and Sanchez-Flores [25] proved $\operatorname{unvd}(TT_{7})=54$ . This result and Proposition 1 imply $\operatorname{unvd}(TT_{n})\leqslant 54\times 2^{n-7}$ for all $n\geqslant 7$ .

The average degree of a nonempty digraph $D$ is the average degree of its underlying graph, that is $2\frac{|A(D)|}{|V(D)|}$ . The maximum average degree of a digraph is the maximum average degree over all its nonempty subdigraphs. Similarly to Erdős and Moser [8], one can show that the unavoidability of an acyclic digraph is exponential in its maximum average degree.

Proposition 2.

Let $D$ be an acyclic digraph with maximum average degree $\alpha$ . Then $\displaystyle\operatorname{unvd}(D)>2^{\alpha/2}$ .

Proof.

Consider a random tournament $T$ on $p\leqslant 2^{\alpha/2}$ vertices. Let $v_{1},\dots,v_{n}$ be a labelling of the vertices of a subdigraph $H$ of $D$ with average degree $\alpha$ . For each ordered $n$ -uple $(w_{1},\dots,w_{n})$ of distinct vertices in $T$ , the probability that $T\langle\{w_{1},\dots,w_{n}\}\rangle$ contains a labelled copy of $H$ (i.e. such that $w_{i}w_{j}$ is an arc in $T$ whenever $v_{i}v_{j}$ is an arc in $H$ ) is $\left(\frac{1}{2}\right)^{|A(H)|}=\left(\frac{1}{2}\right)^{\alpha n/2}$ . Thus the expected number of labelled copies of $H$ is $\frac{p!}{(p-n)!}\left(\frac{1}{2}\right)^{\alpha n/2}<\frac{p^{n}}{2^{\alpha n/2}}=\left(\frac{p}{2^{\alpha/2}}\right)^{n}\leqslant 1$ . ∎

Proposition 2 gives a non-trivial lower bound on the unavoidability of dense acyclic digraphs, that is with maximum average degree larger than logarithmic in their order. However, smaller bounds on the unavoidability are expected for sparse digraphs. In particular, one can ask which families ${\cal F}$ of digraphs are linearly unavoidable, that is such that there exists a constant $C$ such that $\operatorname{unvd}(D)\leqslant C\cdot|V(D)|$ for every digraph $D$ in ${\cal F}$ , and which are polynomially unavoidable, that is such that there exists a polynomial $P$ such that $\operatorname{unvd}(D)\leqslant P(|V(D)|)$ for every digraph $D$ in ${\cal F}$ .

Note that by Proposition 2, the digraphs $D$ of a linearly unavoidable family must have maximum average degree at most $2\log(|V(D)|)+\mathcal{O}(1)$ . For every integer $n$ with $n\geqslant 2$ , Linial, Saks and Sós [19] constructed an $n$ -unavoidable digraph with $n$ vertices and $n\log n-C\cdot n\log\log n$ arcs for some fixed constant $C$ . Those digraphs form a linearly unavoidable family with logarithmic maximum average degree.

Several other classes of acyclic digraphs have been proved to be linearly unavoidable. Much attention has been devoted to oriented paths, oriented trees, and oriented forests which are orientations of paths, trees, and forests respectively. It started with Rédei’s theorem [21] which states that the unavoidability of $\vec{P}_{n}$ , the directed path on $n$ vertices, is exactly $n$ .

Theorem 3 (Rédei [21]).

Every tournament has a Hamiltonian directed path.

In 1971, Rosenfeld [24] conjectured that there is an integer $N>7$ such that $\operatorname{unvd}(P)=|P|$ for every oriented path of order at least $N$ . Several papers gave partial answers to this conjecture [11, 1, 9, 26] until Rosenfeld’s conjecture was verified by Thomason, who proved in [27] Rosenfeld’s conjecture for $N=2^{128}$ . Finally, Havet and Thomassé [15] showed that $\operatorname{unvd}(P)=|V(P)|$ for every oriented path $P$ except the antidirected paths of order $3$ , $5$ , and $7$ .

Regarding oriented trees, Sumner (see [23]) made the following celebrated conjecture.

Conjecture 4 (Sumner).

Every oriented tree of order $n>1$ is $(2n-2)$ -unavoidable.

Since every forest is the subdigraph of a tree, this conjecture is equivalent to the analogue for oriented forests. If true, Sumner’s conjecture would be tight. Indeed, the out-star $S^{+}_{n}$ , which is the digraph on $n$ vertices consisting of a vertex dominating the $n-1$ others, is not contained in the regular tournaments of order $2n-3$ . The first linear upper bound was given by Häggkvist and Thomason [12]. Following improvements of Havet [13], Havet and Thomassé [14], and El Sahili [7], Dross and Havet [6] used the notion of median order to prove that every oriented tree of order $n\geqslant 2$ is $\left\lceil\frac{21}{8}n-\frac{47}{16}\right\rceil$ -unavoidable. Kühn, Mycroft and Osthus [16] proved that Sumner’s conjecture is true for all sufficiently large $n$ .

Theorem 5 (Kühn, Mycroft, and Osthus [16]).

There is an integer $n_{0}$ such that for every $n\geqslant n_{0}$ , every oriented tree of order $n$ is $(2n-2)$ -unavoidable.

Motivated by those results and a work of Lee [18], Bucić, Letzter and Sudakov [3] asked whether the digraphs with bounded maximum average degree are linearly unavoidable. Draganić et al. [5] proved that this is the case for $k$ -th powers of directed paths. The $k$ -th power of a digraph $D$ is the digraph, denoted by $D^{k}$ , with vertex set $V(D)$ in which $uv$ in an arc if and only if $\operatorname{dist}_{D}(u,v)\leqslant k$ . Fox, He, and Widgerson [10] showed that this is not the case in general: they proved that for any $\Delta\geqslant 2$ and any sufficiently large $n$ , there exists an acyclic digraph $D$ with $n$ vertices and maximum degree $\Delta$ such that

\operatorname{unvd}(D)\geqslant n^{\Omega(\Delta^{2/3}/\log^{5/3}\Delta)}.

This result raises the two following questions. Firstly, are the digraphs with bounded maximum average degree polynomially unavoidable?

Problem 6.

Let $\alpha$ be a positive real number. Does there exist a polynomial $P_{\alpha}$ such that $\operatorname{unvd}(D)\leqslant P_{\alpha}(|V(D)|)$ for every digraph with maximum average degree at most $\alpha$ ?

Secondly, which families of acyclic digraphs (with bounded maximum average degree) are linearly unavoidable? In this direction, Fox, He, and Widgerson [10] showed that for every acyclic digraph $D$ of maximum degree $\Delta$ , if there is a partition $S_{1},\dots,S_{h}$ of $V(D)$ such that for every arc $uv$ of $D$ , there exists $i\in[h-1]$ such that $u\in S_{i}$ and $v\in S_{i+1}$ , then $\operatorname{unvd}(D)\leqslant h^{10\Delta\log\Delta}|V(D)|$ .

Our results

In this paper, we give some more partial answers to the above second question by proving some new families of acyclic digraphs to be linearly unavoidable. We are in particular interested in operations to form linearly unavoidable families from others.

Let $k$ be a positive integer. The $k$ -blow-up of a digraph $D$ , denoted by $D[k]$ , is obtained by blowing-up each vertex into an independent set of size $k$ . Formally, $D[k]$ is defined by

	$\displaystyle V(D[k])$	$\displaystyle=$	$\displaystyle\{(v,i)\mid v\in V(D),i\in[k]\},\mbox{ and }$
	$\displaystyle A(D[k])$	$\displaystyle=$	$\displaystyle\{(u,i)(v,j)\mid uv\in A(D),i\in[k],j\in[k],i\neq j\}.$

We believe that if a family $\cal F$ is linearly unavoidable, then the family ${\cal F}[k]=\{D[k]\mid D\in{\cal F}\}$ of its $k$ -blow-ups is also linearly unavoidable.

Conjecture 7.

If $\cal F$ is linearly unavoidable and has bounded maximum average degree, then ${\cal F}[k]$ is also linearly unavoidable.

Observe first that the bounded maximum average degree condition in the above conjecture is necessary. Indeed, for every $n$ , let $D_{n}$ be the digraph of order $n$ which is the disjoint union of a transitive tournament of order $\lfloor\log n\rfloor+1$ and $n-\lfloor\log n\rfloor-1$ isolated vertices. Each $D_{n}$ is clearly $n$ -unavoidable, but $D_{n}[k]$ has maximum average degree $k\lfloor\log n\rfloor$ and so $\operatorname{unvd}(D_{n})\geqslant 2^{k\lfloor\log n\rfloor/2}\geqslant\frac{1}{2}n^{k/2}$ by Proposition 2.

Observe that the $k$ -blow-up of the directed path of order $n$ is contained in the $2k$ -th power of the directed path of order $kn$ . Thus, the result of Draganić et al. [5] implies Conjecture 7 for directed paths. As a more general evidence to this conjecture, we show in Section 3 that it holds for oriented trees (and thus more generally oriented forests). Precisely, we prove in Theorem 18 that the $k$ -blow-up of an oriented tree of order $n$ is $(2^{10+18k}\cdot kn)$ -unavoidable. This upper bound is certainly not tight. However, the maximum average degree of the $k$ -blow-up of a tree of order $n$ is $2k-2k/n$ . Therefore, by Proposition 2, the optimal bound is of the form $2^{\Theta(k)}\cdot kn$ . Hence we are left with the following question.

Problem 8.

What is the infimum of all the constants $C$ such that for every large enough integer $n$ , the $k$ -blow-up of every oriented tree of order $n$ is $(C^{k}\cdot kn)$ -unavoidable?

Generalizing Proposition 1, we believe that adding a vertex cannot affect too much the unavoidability, in a sense that it can at most multiply it by a constant factor.

Conjecture 9.

There exists a constant $C$ such that $\operatorname{unvd}(D)\leqslant C\cdot\operatorname{unvd}(D-v)$ for every acyclic digraph $D$ and for every vertex $v$ of $D$ .

Let $A$ be an acyclic digraph and let $k$ be a positive integer. An acyclic digraph $D$ is a $k$ -extension of $A$ if there exists a set $S$ of $k$ vertices such that $D-S=A$ . The set $S$ is the added set and its vertices are the added vertices. A vertex is universal in a digraph $D$ if $N^{-}(v)\cup N^{+}(v)\cup\{v\}=V(D)$ . A $k$ -extension $D$ of $A$ is full, if its added vertices are universal in $D$ . A $k$ -extension $D$ of $A$ is a $k$ -twin extension, if all added vertices have the same in- and out-neighbourhood in $V(D-S)$ . Conjecture 9, together with Conjecture 4, implies the following.

Conjecture 10.

There is an absolute constant $C$ such that for every integer $k$ , every $k$ -extension of an oriented tree of order $n$ is $C^{k}(2n-2)$ -unavoidable.

More generally, Conjecture 9 would imply the following.

Conjecture 11.

If $\cal F$ is linearly unavoidable, then the family of $k$ -extensions of digraphs in $\cal F$ is also linearly unavoidable.

In Section 4, we prove this last conjecture for the family of oriented trees (and thus also of oriented forest). More precisely; we show in Corollary 25 that every $k$ -extension of a sufficiently large tree $F$ is $\left(2\cdot 3^{\binom{2k+2}{2}}\cdot|V(F)|\right)$ -unavoidable.

This upper bound on the unavoidability of extension of forests is certainly not tight. In Proposition 28, we show that the unavoidability of some $k$ -extensions of the arcless digraph on $n$ vertices is $2^{k}n-o(n)$ as $n\to+\infty$ . Hence we are left with the following analogue to Problem 8.

Problem 12.

What is the minimum function $f$ such that every $k$ -extension of every forest of order $n$ is $(2^{f(k)}\cdot n)$ -unavoidable?

The above-mentioned results show that the function $f$ is at least linear and at most quadratic. The same question applies to any subfamily, starting with that of empty digraphs. Generally, determining the precise value or good approximations of the unavoidability of $k$ -extensions of oriented trees would be interesting. In Section 5, we show an almost tight upper bound on the unavoidability of full $k$ -twin extensions and the exact unavoidability of the full $1$ -extensions of directed paths.

2 Preliminaries

2.1 Basic properties of tournaments

We will make use of the following folklore properties of tournaments.

Lemma 13 ([2, Proposition 2.2.2]).

Let $k$ be a positive integer. Every tournament has at most $2k-1$ vertices of out-degree less than $k$ .

The out-section of a vertex $v$ in a tournament $T$ , denoted by $S^{+}_{T}(v)$ or simply $S^{+}(v)$ , is the set of vertices that can be reached from $v$ by a directed path. Similarly, the in-section of a vertex $v$ in a tournament $T$ , denoted by $S^{-}_{T}(v)$ or simply $S^{-}(v)$ is the set of vertices from which $v$ can be reached by a directed path. We set $s^{+}_{T}(v)=|S^{+}_{T}(v)|$ and $s^{-}_{T}(v)=|S^{-}_{T}(v)|$ . An out-generator (resp. in-generator) of $T$ is a vertex $v$ such that $s^{+}_{T}(v)=|V(T)|$ (resp. $s^{-}_{T}(v)=|V(T)|$ ).

Lemma 14 ([2, Proposition 2.7.6]).

Let $T$ be a tournament and $v$ a vertex of $T$ . In $T$ , $v$ is the initial (resp. terminal) vertex of a directed path of order $s^{+}(v)$ (resp. $s^{-}(v)$ ). In particular, if $v$ is an out-generator (resp. in-generator) of $T$ , then $v$ is the initial vertex (resp. terminal vertex) of a directed Hamiltonian path.

Let $T$ be a tournament, and $A$ and $B$ be two disjoint sets of vertices of $T$ . If every vertex of $A$ dominates every vertex of $B$ , then we write $A\Rightarrow B$ .

Lemma 15.

Let $T$ be a tournament and let $O$ be the set of vertices that are initial vertices of a directed path of order $k$ in $T$ . Then $O\Rightarrow V(T)\setminus O$ .

Proof.

Suppose for contradiction that there exists $u\in V(T)\setminus O$ and $v\in O$ such that $uv\in A(T)$ . Since $v\in O$ , there is a path $P$ of order $k$ in $T$ with initial vertex $v$ . Hence $s^{+}(u)\geqslant|V(P)|\geqslant k$ and so $u$ is the initial vertex of a directed path of order $k$ by Lemma 14. ∎

2.2 Median order

The notion of median order has been introduced in [14], see also [2, Chapter 2] and [5]. A median order of a digraph $D$ is a linear order $(v_{1},v_{2},\ldots,v_{n})$ of its vertex set such that $|\{(v_{i},v_{j})\mid i<j\}|$ , the number of forward arcs (i.e. directed from left to right), is as large as possible. Let us first note some basic properties of median orders of tournaments.

Lemma 16.

Let $T$ be a tournament and $(v_{1},v_{2},\ldots,v_{n})$ a median order of $T$ . Then, for any two indices $i,j$ with $1\leqslant i<j\leqslant n$ :

(M1)

the suborder $(v_{i},v_{i+1},\ldots,v_{j})$ is a median order of the induced subtournament $T\langle\{v_{i},v_{i+1},\ldots,v_{j}\}\rangle$ ;
(M2)

$v_{i}$ dominates at least half of the vertices $v_{i+1},v_{i+2},\ldots,v_{j}$ , and $v_{j}$ is dominated by at least half of the vertices $v_{i},v_{i+1},\ldots,v_{j-1}$ , in particular $v_{i}$ dominates $v_{i+1}$ ;
(M3)

if $v_{i+2}\rightarrow v_{i}$ , then $v_{i-1}\Rightarrow\{v_{i},v_{i+1},v_{i+2}\}$ when $i\geqslant 2$ , and $\{v_{i},v_{i+1},v_{i+2}\}\Rightarrow v_{i+3}$ when $i\leqslant n-3$ ;
(M4)

if $v_{n}\rightarrow v_{1}$ , then there exists $\ell$ such that $v_{1}\rightarrow v_{\ell}\rightarrow v_{n}$ ; moreover, if $|\{\ell\mid v_{1}\rightarrow v_{\ell}\rightarrow v_{n}\}|=1$ , then both $(v_{2},\ldots,v_{n},v_{1})$ and $(v_{n},v_{1},\ldots,v_{n-1})$ are median orders of $T$ ;
(M5)

if $(v_{i}^{\prime},\dots,v_{j}^{\prime})$ is a median order of $T\langle\{v_{i},v_{i+1},\ldots,v_{j}\}\rangle$ , then $(v_{1},\ldots,v_{i-1},v_{i}^{\prime},\dots,v_{j}^{\prime},v_{j+1},\dots,v_{n})$ is also a median order of $T$ .

Proof.

Items (M1), (M2), and (M5) follow easily from the definition.

(M3) Assume for a contradiction that $v_{i+2}\to v_{i}$ but there is an arc from $v_{i},v_{i+1},v_{i+2}$ to $v_{i-1}$ . By (M2) there is exactly one such arc and its tail $u$ belongs to $\{v_{i+1},v_{i+2}\}$ . If $u=v_{i+2}$ , then $v_{i+2}$ has two out-neighbours in $\{v_{i-1},v_{i},v_{i+1}\}$ , contradicting (M2). If $u=v_{i+1}$ , then $(v_{i+1},v_{i-1},v_{i+2},v_{i})$ has less forward arcs than $(v_{i-1},v_{i},v_{i+1},v_{i+2})$ , a contradiction to (M1). By directional duality, we also have $\{v_{i},v_{i+1},v_{i+2}\}\Rightarrow v_{i+3}$ .

(M4) Suppose that $v_{n}\to v_{1}$ . By (M2), $v_{1}$ dominates at least half of $v_{2},\dots,v_{n}$ , and so more than half of $v_{2},\dots,v_{n-1}$ . Symmetrically, $v_{n}$ is dominated by more than half of $v_{2},\dots,v_{n-1}$ . Hence there exists $\ell\in\{2,\dots,n-1\}$ such that $v_{1}\to v_{\ell}\to v_{n}$ . Now suppose that this $\ell$ is unique. Hence $v_{1}$ dominates exactly $\frac{n-1}{2}$ vertices among $v_{2},\dots,v_{n}$ . It follows that the number of forward arcs in $(v_{2},\dots,v_{n},v_{1})$ is $|\{(v_{i},v_{j})\mid 1\leqslant i<j\leqslant n\}|-d^{+}(v_{1})+d^{-}(v_{1})=|\{(v_{i},v_{j})\mid 1\leqslant i<j\leqslant n\}|$ , which is maximum since $(v_{1},\dots,v_{n})$ is a median order. This proves that $(v_{1},\dots,v_{n},v_{1})$ is a median order. Symmetrically, $(v_{n},v_{1},\dots,v_{n-1})$ is a median order too. ∎

2.3 A Kővári-Sós-Turán-like lemma

The following lemma is inspired by the classical result by Kővári, Sós, and Turán [17], and a similar one was recently used in [5].

Lemma 17.

Let $\alpha,\varepsilon$ be two positive reals and $k$ a positive integer. Let $(A,B,E)$ be a bipartite graph with $|A|\geqslant\frac{k}{\frac{1}{2}-\varepsilon}$ and $\displaystyle\alpha\leqslant\frac{\binom{(\frac{1}{2}-\varepsilon)|A|}{k}}{\binom{|A|}{k}}$ , such that $d(v)\geqslant(\frac{1}{2}-\varepsilon)|B|$ for every $v\in A$ . Then there exist $A^{\star}\subseteq A$ and $B^{\star}\subseteq B$ such that

1.

$|A^{\star}|\geqslant k$ ,
2.

$|B^{\star}|\geqslant\alpha|B|$ , and
3.

$A^{\star}$ is complete to $B^{\star}$ .

Proof.

Suppose for contradiction that the result does not hold. We will count by two different methods the number $M$ of pairs $(X,b)$ with $X\subseteq A$ of size $k$ and $b\in B$ such that $X\subseteq N(b)$ . On the first hand, for every $X\subseteq A$ of size $k$ , there are less than $\alpha|B|$ vertices $b$ in $B$ such that $X\subseteq N(b)$ . We thus have

M<\binom{|A|}{k}\alpha|B|.

On the other hand, by Jensen’s inequality, we have

	$\displaystyle M=\sum_{b\in B}\binom{d(b)}{k}$	$\displaystyle\geqslant$	$\displaystyle\|B\|\binom{\frac{1}{\|B\|}\sum_{b\in B}d(b)}{k}=\|B\|\binom{\frac{1}{\|B\|}\sum_{a\in A}d(a)}{k}$
		$\displaystyle\geqslant$	$\displaystyle\|B\|\binom{\frac{\|A\|}{\|B\|}(\frac{1}{2}-\varepsilon)\|B\|}{k}\geqslant\binom{\|A\|}{k}\alpha\|B\|.$

This contradiction proves the lemma. ∎

Note that $\alpha=2^{-\frac{k}{\frac{1}{2}-\varepsilon}}$ satisfies the hypothesis of Lemma 17. Indeed, simple computations show that $\frac{\binom{(\frac{1}{2}-\varepsilon)|A|}{k}}{\binom{|A|}{k}}$ is a non-increasing function of $|A|$ , and as $|A|\geqslant\frac{k}{\frac{1}{2}-\varepsilon}$ we have

\frac{\binom{(\frac{1}{2}-\varepsilon)|A|}{k}}{\binom{|A|}{k}}\geqslant\frac{\binom{k}{k}}{\displaystyle\binom{\frac{k}{\frac{1}{2}-\varepsilon}}{\scriptstyle k}}\geqslant 2^{-\frac{k}{\frac{1}{2}-\varepsilon}}.

3 Blow-ups of oriented trees

In this section, we show that for every fixed integer $k$ , the class of $k$ -blow-ups of oriented trees is linearly avoidable.

Theorem 18.

Let $F$ be an oriented tree of order $n$ and $k$ a positive integer. Every tournament on at least $2^{10+18k}kn$ vertices contains $F[k]$ .

Proof.

We root $F$ on an arbitrary vertex $s$ . Let $q=2^{1+9k}$ , $p=\lceil 2^{5+3^{2}k}k\rceil$ and $\varepsilon=\frac{1}{2q}$ . Observe that we have $\varepsilon\leqslant\frac{1}{6}$ , $q\geqslant 2^{1+\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}}$ , and $p\geqslant q\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}$ . Let $N=\frac{1}{2}(4qn+1)p\leqslant\frac{1}{2}2^{10+18k}k\cdot n$ (using $4qn+1\leqslant 2\times 4qn$ and $p\leqslant 2\times 2^{5+3^{2}k}k$ ) and let $T$ be a tournament of order $2N$ . We will show that $T$ has a subdigraph isomorphic to $F[k]$ . Let $v_{-N},\dots,v_{N-1}$ be a median order of $T$ . We partition $v_{-N},\dots,v_{N-1}$ into $4qn+1$ intervals $V_{i}=\{v_{pi},\dots,v_{p(i+1)-1}\}$ for $i\in\{-2qn,\dots,2qn\}$ . We will find a copy of $F[k]$ in $D$ iteratively, by adding at each step the out-children (i.e. its children which are out-neighbours) or the in-children (i.e. its children which are in-neighbours) of a node in $F$ . Let $F_{1},\dots,F_{r}$ be a sequence of subtrees of $F$ such that

$(i)$

$F_{1}$ is the singleton $\{s\}$ ,
$(ii)$

for every $i\leqslant\frac{r-1}{2}$ , $F_{2i+1}$ is obtained from $F_{2i}$ by adding all the out-children in $F$ of a vertex $x\in V(F_{2i})$ without any out-children in $F_{2i}$ ,
$(iii)$

for every $i\leqslant\frac{r-2}{2}$ , $F_{2i+2}$ is obtained from $F_{2i+1}$ by adding all the in-children in $F$ of a vertex $x\in V(F_{2i+1})$ without any in-children in $F_{2i+1}$ , and
$(iv)$

$F_{r}=F$ .

Observe that such a sequence exists with $r\leqslant 2n-1$ . Moreover, we say that a vertex $x$ in $F_{i}$ is fully processed if all its children in $F$ are also in $F_{i}$ , half processed if all its out-children in $F$ are in $F_{i}$ . Otherwise we say that $x$ is not processed. We prove the following property by induction:

For every $j\in\{1,\dots,r\}$ , there is an injection $\iota:V(F_{j})\to\{-2q|V(F_{j})|,\dots,2q|V(F_{j})|\}$ and for every $x\in V(F_{j})$ there exists a set $U_{x}\subseteq V_{\iota(x)}$ such that

$(i)$

$|U_{x}|\geqslant\frac{k}{\left(\frac{1}{2}-\varepsilon\right)^{2}}$ if $x$ is not processed,
$(ii)$

$|U_{x}|\geqslant\frac{k}{\frac{1}{2}-\varepsilon}$ if $x$ is half processed,
$(iii)$

$|U_{x}|\geqslant k$ if $x$ is fully processed,
$(iv)$

if $xy$ is an arc in $F_{j}$ , then every vertex in $U_{x}$ dominates $U_{y}$ , and

(v)

for every $i\in\{-2q|V(F_{j})|,\dots,2q|V(F_{j})|\}$ a fraction of at most $\frac{1}{q}$ of the elements of the interval $\{i,\dots,2q|V(F_{j})|\}$ (respectively $\{-2q|V(F_{j})|,\dots,i\}$ ) is in $\{\iota(x)\mid x\in V(F_{j})\}$ . More precisely,

	$\displaystyle\|\{i,\dots,2q\|V(F_{j})\|\}\cap\{\iota(x)\mid x\in V(F_{j})\}\|$	$\displaystyle\leqslant\frac{1}{q}\left(2q\|V(F_{j})\|-i+1\right),$
	$\displaystyle\text{and~{}~{}~{}~{}}\|\{-2q\|V(F_{j})\|,\dots,i\}\cap\{\iota(x)\mid x\in V(F_{j})\}\|$	$\displaystyle\leqslant\frac{1}{q}\left(i+2q\|V(F_{j})\|+1\right).$

Observe that, for $j=1$ , setting $\iota(s)=0$ and taking for $U_{s}$ any set in $V_{0}$ of size $p\geqslant\frac{k}{\left(\frac{1}{2}-\varepsilon\right)^{2}}$ satisfies the invariant. Note also that, for $j=r$ , the invariant implies the theorem. Now suppose that the property holds for some $j<r$ . Let $\iota$ and $(U_{x})_{x\in F_{j}}$ witnessing that the property holds at step $j$ . Let $x$ be the vertex in $F_{j}$ such that $F_{j+1}$ is obtained from $F_{j}$ by adding the out-children of $x$ in $F$ , or the in-children of $x$ in $F$ . Our goal is to find a new value $U^{\prime}_{x}$ for $U_{x}$ , and values for $\iota(y),U_{y}$ for every out-children (respectively in-children) $y$ of $x$ .

Case 1:

$F_{j+1}$ is obtained from $F_{j}$ by adding the $\ell$ out-children of $x$ in $F$ .

Let $A=U_{x}$ and $B=\bigcup_{\iota(x)<i\leqslant 2q|V(F_{j})|+q\ell}V_{i}$ . Note that $|B|\geqslant p(2q|V(F_{j})|+\ell q-\iota(x))\geqslant\ell qp$ . We first justify that every vertex in $V_{\iota(x)}$ dominates at least $(\frac{1}{2}-\varepsilon)|B|$ vertices in $B$ . To this purpose, let $v_{i}$ be any vertex in $V_{\iota(x)}$ , so $i\in\{p\iota(x),\dots,p(\iota(x)+1)-1\}$ . Let $X$ be the set of vertices $\{v_{i+1},\dots,v_{p(\iota(x)+1)-1}\}$ , which is disjoint from $B$ ( $X$ is empty if $i=p(\iota(x)+1)-1$ ). Observe that

N^{+}(v_{i})\cap B=\Big{(}N^{+}(v_{i})\cap(X\cup B)\Big{)}\setminus\Big{(}N^{+}(v_{i})\cap X\Big{)}.

Since $X\cup B=\{v_{i+1},\dots,v_{p(\iota(x)+1)-1+|B|}\}$ , and because $v_{-N},\dots,v_{N-1}$ is a median order, by (M2) we have $|N^{+}(v_{i})\cap(X\cup B)|\geqslant\frac{1}{2}|X\cup B|$ . Therefore, we obtain

|N^{+}(v_{i})\cap B|\geqslant\frac{1}{2}|X\cup B|-|X|=\frac{1}{2}|B|-\frac{1}{2}|X|\geqslant\frac{1}{2}(|B|-p)\geqslant\left(\frac{1}{2}-\frac{1}{2q}\right)|B|=\left(\frac{1}{2}-\varepsilon\right)|B|.

This shows that every vertex in $V_{\iota(x)}$ dominates at least $(\frac{1}{2}-\varepsilon)|B|$ vertices in $B$ , and so does every vertex in $A$ . By Lemma 17 applied for $\alpha=2^{-\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}}$ , there exist $A^{\star}\subseteq U_{x}$ and $B^{\star}\subseteq B$ such that every vertex in $A^{\star}$ dominates $B^{\star}$ , $|B^{\star}|\geqslant 2^{-\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}}|B|$ , and $|A^{\star}|\geqslant\frac{k}{\frac{1}{2}-\varepsilon}$ . We set $U^{\prime}_{x}=A^{\star}$ .

Let $I$ be the set of indices $i\in\{\iota(x)+1,\dots,2q|V(F_{j})|+q\ell\}$ such that $|B^{\star}\cap V_{i}|\geqslant\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}$ and $i\notin\{\iota(z)\mid z\in V(F_{j})\}$ . In what follows we show that $I$ is large enough, which will enable us to find $U_{y}$ for every out-child $y$ of $x$ in $F$ .

Claim 1.

$|I|\geqslant\ell$

Proof of claim. Suppose that this does not hold, so $|I|\leqslant\ell-1$ . We define $J,I^{\star},$ and $I^{\iota}$ as follows:

	$\displaystyle J$	$\displaystyle=\{\iota(x)+1,\dots,2q\|V(F_{j})\|+ql\},$
	$\displaystyle I^{\star}$	$\displaystyle=\{i\in J\mid\|V_{i}\cap B^{\star}\|\geqslant\tfrac{k}{(\frac{1}{2}-\varepsilon)^{2}}\},\text{ and}$
	$\displaystyle I^{\iota}$	$\displaystyle=\{\iota(z)\mid z\in V(j)\}\cap J.$

Observe that $I=I^{\star}\setminus I^{\iota}$ by definition. By the induction hypothesis, $|I^{\iota}|\leqslant\frac{1}{q}(|J|-q\ell)$ . Since $|I|\leqslant\ell-1$ by assumption, we obtain $|I^{\star}|\leqslant\ell-1+\frac{1}{q}(|J|-q\ell)=\frac{|J|}{q}-1$ . This leads to the following inequalities, in which we also use $|B|=p|J|$

\begin{split}|B^{\star}|&=\sum_{i\in J\cap I^{\star}}|V_{i}\cap B^{\star}|+\sum_{i\in J\setminus I^{\star}}|V_{i}\cap B^{\star}|\\ &\leqslant\left(\frac{|J|}{q}-1\right)p+\left(\frac{q-1}{q}|J|+1\right)\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}\\ &=\left(\frac{|B|}{q}\right)+\left(\frac{q-1}{q}\frac{|B|}{p}\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}\right)+\left(\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}-p\right)\\ &<\left(\frac{1}{q}+\frac{k}{p(\frac{1}{2}-\varepsilon)^{2}}\right)|B|\\ &\leqslant\frac{2}{q}|B|\\ &\leqslant 2^{-\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}}|B|.\end{split}

This is a contradiction since $|B^{\star}|\geqslant 2^{-\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}}|B|$ . $\lozenge$

We can now extend $\iota$ to the out-children of $x$ by taking values in $I$ , and then we can arbitrarily take $U_{z}\subseteq B^{\star}\cap V_{\iota(z)}$ for every out-child $z$ of $x$ . Recall that $|V(F_{j+1})|=|V(F_{j})|+\ell$ . The invariant still holds because we add $2\ell qp$ vertices at the end and at the beginning of the median order:

$(i)$

For every $i\in\{-2q|V(F_{j})|-2q\ell,\dots,2q|V(F_{j})|\}$ , $|\{i,\dots,2q|V(F_{j})|+2q\ell\}\cap\{\iota(z)\mid z\in V(F_{j+1})\}|\leqslant\frac{1}{q}(2q|V(F_{j})|-i+1)+\ell\leqslant\frac{1}{q}(2q|V(F_{j+1})|-i+1)$ .
$(ii)$

For every $i\in\{2q|V(F_{j})|+1,\dots,2q|V(F_{j})|+q\ell\}$ , $|\{i,\dots,2q|V(F_{j})|+2q\ell\}\cap\{\iota(z)\mid z\in V(F_{j+1})\}|\leqslant\ell\leqslant\frac{1}{q}(q\ell)\leqslant\frac{1}{q}(2q|V(F_{j+1})|-i+1)$ .
$(iii)$

For every $i\in\{2q|V(F_{j})|+q\ell+1,\dots,2q|V(F_{j})|+2q\ell\}$ , $|\{i,\dots,2q|V(F_{j})|+2q\ell\}\cap\{\iota(z)\mid z\in V(F_{j+1})\}|=0\leqslant\frac{1}{q}(2q|V(F_{j+1})|-i+1)$ .
$(iv)$

For every $i\in\{-2q|V(F_{j})|,\dots,2q|V(F_{j})|+2q\ell\}$ , $|\{-2q|V(F_{j})|-2q\ell,\dots,i\}\cap\{\iota(z)\mid z\in V(F_{j+1})\}|\leqslant\frac{1}{q}(i+2q|V(F_{j})|+1)+\ell\leqslant\frac{1}{q}(i+2q|V(F_{j+1})|+1)$ .
$(v)$

For every $i\in\{-2q\ell-2q|V(F_{j})|,\dots,-2q|V(F_{j})|-1\}$ , $|\{-2q|V(F_{j})|-2q\ell,\dots,i\}\cap\{\iota(z)\mid z\in V(F_{j+1})\}|=0\leqslant\frac{1}{q}(i+2q|V(F_{j+1})|+1)$ .

Case 2:

$F_{j+1}$ is obtained from $F_{j}$ by adding the $\ell$ in-children of $x$ in $F$ .

Let $A=U_{\iota(x)}$ and $B=\bigcup_{-2q|V(F_{j})|-q\ell\leqslant i<\iota(x)}V_{i}$ . Since $x$ is half processed, we have $|A|\geqslant\frac{k}{\frac{1}{2}-\varepsilon}$ . Moreover $|B|\geqslant q\ell p$ and every vertex in $A$ is dominated by at least $\frac{1}{2}|B|-|A|\geqslant(\frac{1}{2}-\varepsilon)|B|$ vertices in $B$ . Using Lemma 17, we deduce that there are sets $A^{\star}\subseteq A,B^{\star}\subseteq B$ with $B^{\star}\Rightarrow A^{\star}$ , $|A^{\star}|\geqslant k$ and $|B^{\star}|\geqslant 2^{-\frac{k}{\frac{1}{2}-\varepsilon}}|B|\geqslant 2^{-\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}}|B|$ . We set $U^{\prime}_{x}=A^{\star}$ . We now find $U_{y}$ for every $y$ in-children of $x$ in $F$ . With a proof almost identical to the one of Claim 1 we deduce the following claim.

Claim 2.

There is a set $I\subseteq\{-2q|V(F_{j})|-q\ell,\dots,\iota(x)-1\}$ of size at least $\ell$ such that $\iota(z)\not\in I$ for every $z\in V(F_{j})$ and $|B^{\star}\cap V_{i}|\geqslant\frac{k}{(\frac{1}{2}-\varepsilon)^{2}}$ for every $i\in I$ .

Then we build $U_{y},\iota(y)$ for every in-children $y$ of $x$ as in the first case. This concludes the proof of the theorem.∎

4 Extensions of oriented trees

In this section, we show that for every fixed integer $k$ , the class of $k$ -extensions of oriented trees is linearly unavoidable. Our method is based on the fact that the number of copies of $TT_{2k+1}$ in any $N$ -vertex tournaments is in $\Omega_{k}(N^{2k+1})$ . We start with the case $k=1$ , which is a good warm-up for the general case.

Lemma 19 (Folklore).

Every tournament of order $N$ contains at least $\frac{1}{8}N(N-1)(N-3)$ copies of $TT_{3}$ .

Proof.

Let $T$ be a tournament of order $N$ . Let $\vec{t}$ be the number of directed triangles in $T$ and let $tt_{3}$ be the number of $TT_{3}$ in $T$ . The number of copies of $\vec{P}_{3}$ (the directed path of order $3$ ) in $T$ is $\sum_{v\in V(T)}d^{-}(v)d^{+}(v)\leqslant N\left(\frac{N-1}{2}\right)^{2}=\frac{1}{4}N(N-1)^{2}$ . But the number of $\vec{P}_{3}$ is also $tt_{3}+3\vec{t}=tt_{3}+3(\binom{N}{3}-tt_{3})=3\binom{N}{3}-2tt_{3}$ . We deduce that $3\binom{N}{3}-2tt_{3}\leqslant\frac{1}{4}N(N-1)^{2}$ and so $tt_{3}\geqslant\frac{1}{2}\left(\frac{N(N-1)(N-2)}{2}-\frac{N(N-1)^{2}}{4}\right)=\frac{1}{8}N(N-1)(N-3)$ . ∎

We will also need the following well-known lemma. Recall that a hypergraph $\mathcal{H}$ is a pair $(V,E)$ where $V$ is a finite set and $E$ is a subset of $2^{V}$ . We call the elements of $V$ the vertices of $\mathcal{H}$ , and the elements of $E$ the hyperedges of $\mathcal{H}$ . An hypergraph $\mathcal{H}^{\prime}=(V^{\prime},E^{\prime})$ is a subhypergraph of $\mathcal{H}$ , and we write $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ , if $V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$ .

Lemma 20 (Folklore).

Let $\mathcal{H}$ be a hypergraph on $n$ vertices and with $m$ hyperedges. There is a hypergraph $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ such that every vertex of $\mathcal{H}^{\prime}$ belongs to at least $\frac{m}{n}$ hyperedges of $\mathcal{H}^{\prime}$ .

Proof.

We proceed by induction on $n$ . If every vertex in $\mathcal{H}$ is in at least $\frac{m}{n}$ hyperedges we are done. Otherwise there is a vertex $u$ in less than $\frac{m}{n}$ hyperedges, then $\mathcal{H}-u$ has $m^{\prime}\geqslant m-\frac{m}{n}=\frac{m}{n}(n-1)$ hyperedges and $n^{\prime}=n-1$ vertices. Hence, by the induction hypothesis, $\mathcal{H}-u$ has a subhypergraph with minimum degree at least $\frac{m^{\prime}}{n^{\prime}}\geqslant\frac{m}{n}$ as wanted. ∎

Given an acyclic digraph $D$ , we denote by $\operatorname{unvd}^{*}(D)$ the maximum of $\operatorname{unvd}(H)+|V(D)\setminus V(H)|$ over all the subdigraphs $H$ of $D$ .

Theorem 21.

Let $D$ be a $1$ -extension of an oriented tree $F$ on $n$ vertices, then $\operatorname{unvd}(D)\leqslant 8\operatorname{unvd}^{*}(F)+3$ .

By applying Theorem 5 to bound $\operatorname{unvd}^{*}(F)$ , we obtain the following.

Corollary 22.

There exists a constant $n_{0}$ such that the following holds. Let $D$ be a $1$ -extension of an oriented tree $F$ on at least $n_{0}$ vertices, then $\operatorname{unvd}(D)\leqslant 16|V(F)|-13$ .

An embedding $\varphi\colon H\to D$ of a digraph $H$ in a digraph $D$ is an injective function $\varphi\colon V(H)\to V(D)$ such that $\varphi(u)\varphi(v)\in A(D)$ for every $uv\in A(H)$ . Observe that $G$ contains a copy of $H$ if and only if there is an embedding of $H$ in $G$ .

Proof of Theorem 21.

Let $D$ be a $1$ -extension of $F$ with added vertex $s$ . We assume that $D$ is a full $1$ -extension of $F$ , for otherwise we just add missing arcs. Let $T$ be a tournament on $N=8\operatorname{unvd}^{*}(F)+3$ vertices. By Lemma 19, the number of $TT_{3}$ in $T$ is at least $\frac{1}{8}N(N-1)(N-3)$ . We deduce that there is a vertex $t$ which is the middle vertex (i.e. the vertex with in- and out-degree $1$ ) of at least $\frac{1}{8}(N-1)(N-3)$ copies of $TT_{3}$ in $T$ . In other words there are at least $\frac{1}{8}(N-1)(N-3)$ arcs from $N^{-}(t)$ to $N^{+}(t)$ . Consider the bipartite graph $H_{0}=(N^{-}_{T}(t),N^{+}_{T}(t),E)$ where $E=\{uw\in A(T)\mid u\in N^{-}_{T}(t),w\in N^{+}_{T}(t)\}$ . By Lemma 20, $H_{0}$ has a nonempty subgraph $H$ with minimum degree at least $\frac{(N-1)(N-3)}{8(N-1)}=\frac{1}{8}(N-3)\geqslant\operatorname{unvd}^{*}(F)$ . Let $A=V(H)\cap N^{-}_{T}(v),B=V(H)\cap N^{+}_{T}(t)$ . Since $H$ is bipartite, note that in particular $|A|,|B|\geqslant\operatorname{unvd}^{*}(F)$ .

We will now inductively build and embedding $\varphi\colon F\to T\langle V(H)\rangle$ such that

•

for every $y\in N^{-}_{D}(s)$ , $\varphi(y)\in A$ , and
•

for every $y\in N^{+}_{D}(s)$ , $\varphi(y)\in B$ .

Extending such an embedding of $F$ by setting $\varphi(s)=t$ yields the desired embedding of $D$ in $T$ .

If $F$ is empty, then the result is clear. Suppose now that $F$ is not empty and consider the tree $F^{\prime}$ obtained from $F$ by contracting every connected component $C$ of $D\langle N^{-}_{D}(s)\rangle$ and $D\langle N^{+}_{D}(s)\rangle$ into a single vertex $u_{V(C)}$ . Consider a leaf $u_{Z}$ of $F^{\prime}$ , and without loss of generality, assume that $Z\subseteq N^{-}_{D}(s)$ . If $Z=V(F)$ , then $V(F)\subseteq N^{-}_{D}(s)$ , and we can embed $F$ in $T\langle A\rangle$ since $|A|\geqslant\operatorname{unvd}^{*}(F)\geqslant\operatorname{unvd}(F)$ . Otherwise, assume by induction that we have an embedding $\varphi\colon F-Z\to T\langle V(H)\rangle$ with $\varphi(N^{-}_{D}(s)\setminus Z)\subseteq A$ and $\varphi(N^{+}_{D}(s))\subseteq B$ . Let $uv$ be the arc joining $Z$ to $F-Z$ in $F^{\prime}$ . Observe that we have $u\in Z$ and $v\in N^{+}_{D}(s)$ , for otherwise $uvs$ is a directed triangle in $D$ , a contradiction to $D$ being acyclic.

As $H$ has minimum degree at least $\operatorname{unvd}^{*}(F)$ , and because $\varphi(v)\in B$ , the size of $A\cap N^{-}_{T}(\varphi(v))$ is at least $\operatorname{unvd}^{*}(F)$ , hence there are at least $\operatorname{unvd}^{*}(F)-|V(F)\setminus Z|\geqslant\operatorname{unvd}(F\langle Z\rangle)$ vertices in $A\cap N^{-}_{T}(\varphi(v))\setminus\varphi(V(F-Z))$ . Thus we can extend $\varphi$ to the vertices in $F\langle Z\rangle$ in $A\cap N^{-}_{T}(\varphi(v))\setminus\varphi(V(F-Z))$ , and this gives the desired embedding of $D$ . See Figure 1 for an illustration. ∎

Figure 1: Illustration of the proof of Theorem 21. The red vertices are the image of

V(F-Z)

under

\varphi

. The green vertices represent an embedding of

F\langle Z\rangle

in the set

A\cap N^{-}_{T}(\varphi(v))\setminus\varphi(V(F-Z))

, which is dashed in the figure.

We now move to the general case. We first prove an analogue of Lemma 19 for larger values of $k$ .

Lemma 23.

Let $k$ be a positive integer and let $T$ be a tournament on $N\geqslant 3^{\binom{k+1}{2}}$ vertices. Then the number of distinct copies of $TT_{k}$ in $T$ is at least $3^{-\binom{k+1}{2}}N^{k}$ .

Proof.

We proceed by induction on $k$ . For $k=1$ the result is clear. Now suppose $k>1$ and that the result holds for smaller values of $k$ . By Proposition 13, in $T$ there are at least $\frac{N}{3}$ vertices of out-degree at least $\frac{N}{3}$ . For every such vertex $u$ , there are by induction at least $3^{-\binom{k}{2}}\left(\frac{N}{3}\right)^{k-1}$ copies of $TT_{k-1}$ in the subtournament induced by $N^{+}(u)$ . Together with $u$ , this gives as many copies of $TT_{k}$ in $T$ . We conclude that the number of copies of $TT_{k}$ in $T$ is at least $\frac{N}{3}\times 3^{-\binom{k}{2}}\left(\frac{N}{3}\right)^{k-1}=3^{-\binom{k+1}{2}}N^{k}$ . ∎

This bound could be improved to $(2^{-\binom{k}{2}}+o(1))N^{k}$ , see [4].

Theorem 24.

Let $k,n$ be integers with $k\geqslant 1,n\geqslant 2$ and let $F$ be an oriented tree of order $n$ . Let $D$ be a $k$ -extension of $F$ , then $\operatorname{unvd}(D)\leqslant 3^{\binom{2k+2}{2}}\cdot\operatorname{unvd}^{*}(F)$ .

Again, applying Theorem 5 to bound $\operatorname{unvd}^{*}(F)$ , we deduce the following corollary.

Corollary 25.

There is a constant $n_{0}$ such that the following holds. Let $D$ be a $k$ -extension of an oriented tree $F$ on at least $n_{0}$ vertices, then $\operatorname{unvd}(D)\leqslant 2\cdot 3^{\binom{2k+2}{2}}\cdot|V(F)|$ .

Proof of Theorem 24.

Let $T$ be a tournament on $N=3^{\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)$ vertices.

Let $H$ be a copy of $TT_{2k+1}$ with acyclic ordering $(u^{\prime}_{0},u_{1},u^{\prime}_{1},\dots,u_{k},u^{\prime}_{k})$ . By Lemma 23, $T$ contains at least $3^{2k\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)^{2k+1}$ copies of $H$ . By the Pigeon-hole Principle, there are $k$ vertices $v_{1},\dots,v_{k}$ in $T$ such that there are at least $\frac{1}{N^{k}}3^{2k\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)^{2k+1}=3^{k\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)^{k+1}$ embeddings of $H$ in $T$ with $u_{i}$ mapped to $v_{i}$ for every $i\in\{1,\dots,k\}$ . From now on, let us say that an embedding $\varphi\colon H\to T$ is valid if $\varphi(u_{i})=v_{i}$ for every $i\in\{1,\dots,k\}$ .

We consider the hypergraph $\mathcal{H}$ with vertex set $V(T)\setminus\{v_{1},\dots,v_{k}\}$ which contains as a hyperedge $\{\varphi(u_{i}^{\prime})\mid 0\leqslant i\leqslant k\}$ for every valid embedding $\varphi\colon H\to T$ . By Lemma 20 applied to $\mathcal{H}$ , there is a set of vertices $X\subseteq V(\mathcal{H})$ such that every vertex in $X$ has degree at least $\frac{1}{N}3^{k\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)^{k+1}$ in $\mathcal{H}$ . Let $(X_{0},\dots,X_{k})$ be the partition of $X$ where $X_{i}$ contains all the vertices $x\in X$ such that $x=\varphi(u_{i}^{\prime})$ for some valid embedding $\varphi\colon H\to T$ .

For all $i,j\in\{0,\dots,k\}$ with $i<j$ and for every vertex $x\in X_{i}$ , we claim that $x$ has at least $\frac{1}{N^{k}}3^{k\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)^{k+1}=\operatorname{unvd}^{*}(F)$ out-neighbours in $X_{j}$ . Assume that this is not the case, then the degree of $x$ in $\mathcal{H}\langle X\rangle$ , which is exactly the number of valid embedding $\varphi\colon H\to T$ with the extra conditions $\varphi(u_{i}^{\prime})=x$ and $\varphi(u_{\ell}^{\prime})\in X$ for every $\ell\in\{0,\dots,k\}$ , is at most

|N^{+}(x)\cap X_{j}|\cdot\prod_{\ell\in\{0,\dots,k\}\setminus\{i,j\}}|X_{\ell}|<N^{k-1}\frac{1}{N^{k}}3^{k\binom{2k+2}{2}}\operatorname{unvd}^{*}(F)^{k+1},

a contradiction to the choice of $X$ . Similarly, if $j<i$ then $x$ has at least $\operatorname{unvd}^{*}(F)$ in-neighbours in $X_{j}$ . Since $k\geqslant 1$ , this implies in particular that $|X_{i}|\geqslant\operatorname{unvd}^{*}(F)$ for every $i\in\{0,\dots,k\}$ .

Let $D$ be a full $k$ -extension of $F$ . As $D$ is acyclic, let $\sigma$ be a topological ordering of $V(D)$ . Let $W\subseteq V(D)$ be such that $F=D-W$ and $w_{1},\dots,w_{k}$ the ordering of $W$ with respect to $\sigma$ . We let $Y_{0},\dots,Y_{k}$ be the partition of $V(F)$ where $Y_{i}$ contains every vertex between $w_{i}$ and $w_{i+1}$ in $\sigma$ , for every $i\in\{1,\dots,k-1\}$ , $Y_{0}$ contains every vertex before $w_{1}$ in $\sigma$ , and $Y_{k}$ contains every vertex after $w_{k}$ in $\sigma$ . By construction, every arc between $Y_{i}$ and $Y_{j}$ in $F$ is from $Y_{i}$ to $Y_{j}$ if $i<j$ . We will now construct by induction on $|V(F)|$ an embedding $\varphi\colon F\to T\langle X\rangle$ such that $\varphi(Y_{i})\subseteq X_{i}$ for every $i\in\{0,\dots,k\}$ . By setting $\varphi(w_{i})=v_{i}$ for every $i\in[k]$ , we will get the desired embedding of $D$ in $T$ .

If $F$ is empty, then the result is clear. Now assume $|V(F)|>0$ . Consider the tree $F^{\prime}$ obtained from $F$ by contracting every connected component $C$ of $D\langle Y_{i}\rangle$ into a single vertex $x_{V(C)}$ , for every $i\in\{0,\dots,k\}$ . Let $x_{Z}$ be a leaf of $F^{\prime}$ and $i\in\{0,\dots,k\}$ be the index such that $Z\subseteq Y_{i}$ . If $Z=V(F)$ , then, as $|X_{i}|\geqslant\operatorname{unvd}^{*}(F)\geqslant\operatorname{unvd}(F)$ , there is an embedding $\varphi$ of $F$ into $T\langle X_{i}\rangle$ and we are done. Otherwise let $p$ be the unique neighbour in $F$ of a vertex in $Z$ which does not belong to $Z$ . Assume that $p$ is the tail of the (unique) arc between $F-Z$ and $Z$ , the other case being symmetric. Let $j\in\{0,\dots,k\}$ be the index such that $p\in Y_{j}$ . Recall that, by construction, we have $j<i$ . By induction hypothesis, there is an embedding $\varphi\colon F-Z\to T\langle X_{0}\cup\dots\cup X_{k}\rangle$ such that $\varphi(Y_{\ell}\setminus Z)\subseteq X_{\ell}$ for every $\ell\in\{0,\dots,k\}$ . We know that $\varphi(p)$ has at least $\operatorname{unvd}^{*}(F)$ in-neighbours in $X_{i}$ . Moreover $\operatorname{unvd}^{*}(F)-|V(F)\setminus Z|\geqslant\operatorname{unvd}(F\langle Z\rangle)$ and so $|X_{i}\cap N^{-}(\varphi(p))\setminus\varphi(V(F-Z))|\geqslant\operatorname{unvd}(F\langle Z\rangle)$ (by definition of $\operatorname{unvd}^{*}(F)$ ). It follows that $F\langle Z\rangle$ can be embedded in $X_{i}\cap N^{-}(\varphi(p))\setminus\varphi(V(F-Z))$ . This gives the desired embedding of $F$ and concludes the proof of the theorem. ∎

5 Particular extensions of some particular forests

5.1 Twin extensions of arcless digraphs

For every positive integers $k,n_{1},n_{2}$ , let $D_{k}(n_{1},n_{2})$ be full $k$ -twin-extension of the arcless digraph $D$ of order $n_{1}+n_{2}$ in which the $k$ added vertices have the same in-neighbourhood $V_{1}$ of size $n_{1}$ and the same out-neighbourhood $V_{2}$ of size $n_{2}$ (with $V_{1},V_{2}$ a partition of $V(D)$ ). Note that $D_{1}(n_{1},n_{2})$ is simply the oriented star made of a vertex dominated by $n_{1}$ vertices and dominating $n_{2}$ vertices.

Proposition 26.

For every positive integers $n,n_{1},n_{2}$ with $n=n_{1}+n_{2}+1$ , each of the following holds

1.

$\operatorname{unvd}(D_{1}(0,n-1))=\operatorname{unvd}(D_{1}(n-1,0))=2n-2$ , and
2.

$\operatorname{unvd}(D_{1}(n_{1},n_{2}))=2n-3$ .

Proof.

The fact that $\operatorname{unvd}(D_{1}(0,n-1))=\operatorname{unvd}(D_{1}(n-1,0))\leqslant 2n-2$ and $\operatorname{unvd}(D_{1}(n_{1},n_{2}))\leqslant 2n-3$ follows from Lemma 13. For the lower bounds, consider first any $(n-2)$ -regular tournament $T$ . Then $T$ has $2n-3$ vertices and does not contain $D_{1}(0,n-1)$ . Thus $\operatorname{unvd}(D_{1}(0,n-1))=\operatorname{unvd}(D_{1}(n-1,0))\geqslant 2n-2$ . Similarly, if $T_{1}$ is an $(n_{1}-1)$ -regular tournament and $T_{2}$ an $(n_{2}-1)$ -regular tournament, then $T_{1}\Rightarrow T_{2}$ is a tournament of order $2n-4$ which does not contain $D_{1}(n_{1},n_{2})$ , implying that $\operatorname{unvd}(D_{1}(n_{1},n_{2}))\geqslant 2n-3$ . ∎

To prove a lower bound on $\operatorname{unvd}(D_{k}(0,n))$ , we will use a probabilistic argument relying on Chernoff’s bound.

Proposition 27 (Chernoff’s Bound).

If $X$ is a random variable following a binomial law with parameters $p\in[0,1]$ and $n\geqslant 0$ , then for every $\varepsilon\in[0,1]$

\mathbf{Pr}[X\geqslant(1+\varepsilon)pn]\leqslant\exp\left(-\frac{\varepsilon^{2}}{3}pn\right).

Proposition 28.

For every fixed $k\geqslant 1$ , $\operatorname{unvd}(D_{k}(0,n))=2^{k}n-o(n)$ as $n\to+\infty$ .

Proof.

The added vertices of $D_{k}(0,n)$ are sources, so by Proposition 1, $\operatorname{unvd}(D_{k}(0,n))\leqslant 2^{k}n$ .

To prove the lower bound, let $0<\varepsilon<1$ and let $T$ be a tournament of order $\left\lfloor\frac{2^{k}}{1+\varepsilon}n+k\right\rfloor$ taken uniformly at random. For every $X\subseteq V(T)$ of size $k$ , let $d^{+}_{X}$ be the number of common out-neighbours of the vertices in $X$ , that is $d^{+}_{X}=|\bigcap_{x\in X}N^{+}(x)|$ . Then $d^{+}_{X}$ follows a binomial law with parameters $2^{-k}$ and $\left\lfloor\frac{2^{k}}{1+\varepsilon}n\right\rfloor\leqslant\frac{2^{k}}{1+\varepsilon}n$ . By Chernoff’s bound (Proposition 27),

\begin{split}\mathbf{Pr}[d^{+}_{X}\geqslant n]&\leqslant\mathbf{Pr}\big{[}d^{+}_{X}\geqslant(1+\varepsilon)\mathbf{E}[d^{+}_{X}]\big{]}\\ &\leqslant\exp\left(-\frac{\varepsilon^{2}}{3}\mathbf{E}[d^{+}_{X}]\right)\\ &\leqslant\exp\left(-\frac{\varepsilon^{2}}{3}2^{-k}\left\lfloor\frac{2^{k}}{1+\varepsilon}n\right\rfloor\right)\\ &\leqslant\exp\left(-\frac{\varepsilon^{2}}{3(1+\varepsilon)}n+1\right).\\ \end{split}

It follows by the Union Bound that $\displaystyle\mathbf{Pr}[T\text{ contains }D_{k}(0,n)]\leqslant\binom{\lfloor\frac{2^{k}}{1+\varepsilon}n\rfloor}{k}\mathrm{e}^{-\frac{\varepsilon^{2}}{3(1+\varepsilon)}n+1}<1$ for $n$ large enough. This proves that $\operatorname{unvd}(D_{k}(0,n))>\left\lfloor\frac{2^{k}}{1+\varepsilon}n+k\right\rfloor$ for $n$ large enough. ∎

We will now prove a similar upper bound for $D_{k}(n_{1},n_{2})$ . To do so, we will use Ramsey’s theorem, that we first recall here.

Theorem 29 (Ramsey’s theorem [20]).

For every positive integers $k$ , $a$ and $b$ , there exists $R_{k}(a,b)$ such that for every $2$ -colouring of the $k$ -subsets of $[R_{k}(a,b)]$ , either there is a set $X\subseteq[R_{k}(a,b)]$ of size $a$ such that every $k$ -subset of $X$ is coloured $1$ , or there is a set $Y\subseteq[R_{k}(a,b)]$ of size $b$ such that every $k$ -subset of $Y$ is coloured $2$ .

Theorem 30.

Let $\varepsilon>0$ and let $k$ be a positive integer. There is a constant $C$ depending only on $k$ and $\varepsilon$ such that $\operatorname{unvd}(D_{k}(n_{1},n_{2}))\leqslant(2^{k}+\varepsilon)(n_{1}+n_{2})+C$ .

Proof.

For fixed constants $k,\varepsilon$ , simple computations show the existence of constants $C_{0}\in\mathbb{N},\eta>0$ such that $\frac{\binom{C}{k}}{\binom{C(\frac{1}{2}-\eta)}{k}}\leqslant 2^{k}+\varepsilon$ for every integer $C\geqslant C_{0}$ . We let $C$ be the maximum between $C_{0}$ and $R_{k}\left(\left\lceil\frac{k}{\frac{1}{2}-\eta}\right\rceil,\left\lceil\frac{k}{\frac{1}{2}-\eta}\right\rceil\right)$ .

We first assume that $n_{1},n_{2}\geqslant\frac{C}{\eta(2^{k}+\varepsilon)}$ . Let $T$ be a tournament on $\lceil(2^{k}+\varepsilon)n_{1}\rceil+\lceil(2^{k}+\varepsilon)n_{2}\rceil+C$ vertices. Consider a median order of $T$ and let $B_{1}$ be the first $\lceil(2^{k}+\varepsilon)n_{1}\rceil$ vertices in this order, $B_{2}$ be the last $\lceil(2^{k}+\varepsilon)n_{2}\rceil$ vertices, and $A$ be set of the remaining $C$ vertices in the middle.

By (M2), every vertex $v\in A$ is dominated by at least $\frac{1}{2}|B_{1}|-|A|\geqslant(\frac{1}{2}-\eta)|B_{1}|$ vertices in $B_{1}$ (using $|B_{1}|=\lceil(2^{k}+\varepsilon)n_{1}\rceil\geqslant\frac{C}{\eta}=\frac{|A|}{\eta}$ ). Let $A^{\prime}\subseteq A$ be any set of size $\left\lceil\frac{k}{\frac{1}{2}-\eta}\right\rceil$ . By Lemma 17, there is a subset $A^{\star}$ of $A^{\prime}$ of size $k$ such that $A^{\star}$ has at least $n_{1}$ common in-neighbours in $B_{1}$ . Since this holds for every subset $A^{\prime}$ of size $\left\lceil\frac{k}{\frac{1}{2}-\eta}\right\rceil$ , and by choice of $C$ , by Ramsey’s Theorem there is a subset $\tilde{A}$ of $A$ of size $\left\lceil\frac{k}{\frac{1}{2}-\eta}\right\rceil$ such that every subset of $k$ vertices in $\tilde{A}$ have at least $k$ common in-neighbours in $B_{1}$ . By repeating the same reasoning, because every vertex in $A$ dominates at least $\frac{1}{2}|B_{2}|-|A|\geqslant(\frac{1}{2}-\eta)|B_{2}|$ vertices in $B_{2}$ , we deduce that $\tilde{A}$ contains a set $X$ of $k$ vertices with at least $n_{2}$ common out-neighbours in $B_{2}$ . Since every $k$ -subset of $\tilde{A}$ has at least $n_{1}$ common in-neighbours in $B_{1}$ , this gives the desired copy of $D_{k}(n_{1},n_{2})$ .

We now consider the case $n_{1}<\frac{C}{\eta(2^{k}+\varepsilon)}$ or $n_{2}<\frac{C}{\eta(2^{k}+\varepsilon)}$ . We apply the previous case for $n_{1},n_{2}$ replaced respectively by $n_{1}+\left\lceil\frac{C}{\eta(2^{k}+\varepsilon)}\right\rceil$ and $n_{2}+\left\lceil\frac{C}{\eta(2^{k}+\varepsilon)}\right\rceil$ . This shows that $\operatorname{unvd}(D_{k}(n_{1},n_{2}))\leqslant(2^{k}+\varepsilon)\left(n_{1}+n_{2}+2\left(\frac{C}{\eta(2^{k}+\varepsilon)}+1\right)\right)+C\leqslant(2^{k}+\varepsilon)(n_{1}+n_{2})+C^{\prime}$ for $C^{\prime}=C+2(2^{k}+\varepsilon)\left(\frac{C}{\eta(2^{k}+\varepsilon)}+1\right)$ . ∎

While Proposition 28 shows that this upper is tight when $n_{1}$ or $n_{2}$ is in $o(n)$ , we do not know the precise asymptotic of $\operatorname{unvd}(D_{k}(n_{1},n_{2}))$ when $n_{1}\approx n_{2}$ .

5.2 $1$ -extensions of directed paths

In this section, we give the exact value of $\operatorname{unvd}(D)$ when $D$ is a full $1$ -extension of a directed path.

Theorem 31.

Let $D$ be a full $1$ -extension of a directed path with added vertex $s$ . If $s$ is a source or a sink, or if $D$ is $TT_{3}$ , then $\operatorname{unvd}(D)=2|V(D)|-2$ . Otherwise, $\operatorname{unvd}(D)=2|V(D)|-3$ .

Proof.

Observe that every orientation of $K_{4}$ contains $TT_{3}$ , and that the directed triangle does not contain $TT_{3}$ , so $\operatorname{unvd}(TT_{3})=4$ . We now assume that $D$ is not $TT_{3}$ .

Set $n=|V(D)|$ , and let $s$ be a vertex of $D$ such that $D-s$ is a directed path $P$ . Let $V_{1}=N^{-}_{D}(s)$ and $V_{2}=N^{+}_{D}(s)$ and set $n_{1}=|V_{1}|$ and $n_{2}=|V_{2}|$ . Observe that $D=D_{1}(n_{1},n_{2})$ . By Proposition 26 we obtain $\operatorname{unvd}(D)\geqslant 2n-3$ , and $\operatorname{unvd}(D)\geqslant 2n-2$ if $s$ is a sink or a source.

If $n_{1}=0$ or $n_{2}=0$ , then $s$ is a source or a sink. Thus, by Proposition 1, we have $\operatorname{unvd}(D)\leqslant 2\operatorname{unvd}(P)=2n-2$ .

It remains to show that $\operatorname{unvd}(D)\leqslant 2n-3$ , assuming $n_{1}\geqslant 1$ and $n_{2}\geqslant 1$ , and $\max\{n_{1},n_{2}\}\geqslant 2$ . By directional duality, assume without loss of generality that $n_{1}\geqslant 2$ . Let $T$ be a tournament of order $2n-3$ , and let $\sigma_{0}=(v_{-2n_{1}+1},\dots,v_{0},\dots,v_{2n_{2}-1})$ be a median order of $T$ . Set $A_{1}=\{v_{-2n_{1}+1},\dots,v_{-1}\}$ and $A_{2}=\{v_{0},\dots,v_{2n_{2}-1}\}$ . Let $B_{1}=N^{-}(v_{-1})\cap A_{1}$ and $B_{2}=N^{+}(v_{-1})\cap A_{2}$ . Observe that, by (M2), $|B_{2}|\geqslant n_{2}$ and $|B_{1}|\geqslant n_{1}-1$ . We first consider the case $|B_{1}|\geqslant n_{1}$ .

Claim 3.

If $|B_{1}|\geqslant n_{1}$ , then $T$ contains a copy of $D$ with $s=v_{-1}$ .

Proof of claim. Let $I^{-}$ be the set of in-generators of $T\langle B_{1}\rangle$ and $O^{+}$ be the set of vertices which are initial vertices of a directed path of order $n_{2}$ in $T\langle B_{2}\rangle$ . Note that $I^{-}\neq\emptyset$ and $O^{+}\neq\emptyset$ . Moreover, by Lemma 15, $(B_{1}\setminus I^{-})\Rightarrow I^{-}$ and $O^{+}\Rightarrow(B_{2}\setminus O^{+})$ . Let $v_{i^{-}}$ be the vertex in $I^{-}$ with largest index and $v_{i^{+}}$ be the vertex in $O^{+}$ with smallest index. By Lemma 14, $v_{i^{-}}$ is the terminus of a directed path $P^{-}$ of order $n_{1}$ in $T\langle B_{1}\rangle$ and $v_{i^{+}}$ is the initial vertex of a directed path $P^{+}$ of order $n_{2}$ in $T\langle B_{2}\rangle$ . Hence we may assume $v_{i^{+}}\rightarrow v_{i^{-}}$ , for otherwise the union of $v_{-1}$ , $P^{-}$ , $P^{+}$ , the arcs between those paths and $v_{-1}$ , and $v_{i^{-}}v_{i^{+}}$ is a copy of $D$ in $T$ .

Assume first that $|B_{2}|=n_{2}$ . Then, since $|A_{2}|=2n_{2}$ , $v_{-1}$ has exactly $n_{2}$ out-neighbour and $n_{2}$ in-neighbours in $A_{2}$ . Consequently $\sigma^{\prime}=(v_{-2n_{1}+1},\dots v_{-2},v_{0},\dots,v_{2n_{2}-1},v_{-1})$ is also a median order of $T$ . By (M4) for $\sigma^{\prime}$ , since $v_{i^{+}}\rightarrow v_{i^{-}}$ , there is a vertex $v_{\ell}$ in $\{v_{i^{-}},\dots,v_{i^{+}}\}\setminus\{v_{-1}\}$ such that $v_{i^{-}}\rightarrow v_{\ell}\rightarrow v_{i^{+}}$ . Observe that $v_{\ell}\notin I^{-}$ by maximality of $i^{-}$ and $v_{\ell}\notin(B_{1}\setminus I^{-})$ because $(B_{1}\setminus I^{-})\Rightarrow\{v_{i^{-}}\}$ . Thus $v_{\ell}\notin B_{1}$ , and similarly $v_{\ell}\notin B_{2}$ . In particular, $v_{\ell}\notin(V(P^{-})\cup V(P^{+}))$ . If $v_{-1}\rightarrow v_{\ell}$ , remove the end-vertex from $P^{+}$ , otherwise remove the initial vertex of $P^{-}$ . In both cases, the resulting union of $v_{-1}$ , $P^{-}$ , $P^{+}$ and the arcs between those paths and $v_{-1}$ is a copy of $D$ in $T$ (with $s=v_{-1}$ ) as desired.

Henceforth, we may assume that $|B_{2}|>n_{2}$ . In particular it implies $|O^{+}|\geqslant 2$ : to see this, take any Hamiltonian directed path of $T\langle B_{2}\rangle$ (which exists by Theorem 3), then the two first vertices of this directed path are initial vertices of directed paths of order $n_{2}$ in $T\langle B_{2}\rangle$ . If there is a vertex $v_{\ell}$ in $\{v_{i^{-}},\dots,v_{i^{+}}\}\setminus\{v_{-1}\}$ such that $v_{i^{-}}\rightarrow v_{\ell}\rightarrow v_{i^{+}}$ , then as above there is a copy of $D$ in $T$ (with $s=v_{-1}$ ), so assume that there is no such $v_{\ell}$ . Hence, by (M4) and (M5), $\tilde{\sigma}=(v_{-2n_{1}+1},\dots,v_{i^{-}-1},v_{i^{-}+1},\dots,v_{i^{+}},v_{i^{-}},v_{i^{+}+1},\ldots,v_{2n_{2}-1})$ is a median order of $T$ . Let $v_{j^{+}}$ be the vertex of smallest index in $O^{+}\setminus\{v_{i^{+}}\}$ . Let $Q^{+}$ be a directed path of order $n_{2}$ in $T\langle B_{2}\rangle$ with initial vertex $v_{j^{+}}$ . If $v_{i^{-}}\rightarrow v_{j^{+}}$ , then the union of $v_{-1}$ , $P^{-}$ , $Q^{+}$ , the arcs between those paths and $v_{-1}$ , and $v_{i^{-}}v_{j^{+}}$ is a copy of $D$ in $T$ . Henceforth we may assume $v_{j^{+}}\rightarrow v_{i^{-}}$ . By (M4) for $\tilde{\sigma}$ , there is a vertex $v_{p}$ with $i^{+}+1\leqslant p\leqslant j^{+}-1$ such that $v_{i^{-}}\rightarrow v_{p}\rightarrow v_{j^{+}}$ . Note that $v_{p}\neq v_{-1}$ because $i^{+}\geqslant 0$ , and as above $v_{p}\notin B_{1}\cup B_{2}$ . As above, by removing either the end-vertex of $Q^{+}$ or the initial vertex of $P^{-}$ , we get that the union of $v_{-1}$ , $P^{-}$ , $Q^{+}$ and the arcs between those paths and $v_{-1}$ is a copy of $D$ in $T$ . $\lozenge$

Since Claim 3 settles the case $|B_{1}|\geqslant n_{1}$ , and because $|B_{1}|\geqslant n_{1}-1$ , we now assume that $|B_{1}|=n_{1}-1$ . Then by (M4) and (M5) applied on $\sigma_{0}$ , we have that $\sigma_{1}=(v_{-1},v_{-2n_{1}+1},\dots,v_{-2},v_{0},\dots,v_{2n_{2}-1})$ is a median order of $T$ . In particular this implies $v_{-2}\rightarrow v_{0}$ and $v_{-1}\rightarrow v_{-2n_{1}+1}$ . Observe that $v_{-1},v_{-2n_{1}+1},\dots,v_{-1}$ is then a Hamiltonian directed cycle of $T\langle A_{1}\rangle$ . Not also that if $|N^{-}(v_{2})\cap A_{1}|\geqslant n_{1}$ we can apply Claim 3 with $\sigma_{1},v_{-2}$ playing the roles of $\sigma_{0},v_{-1}$ respectively. By repeating this process, either we eventually find a copy of $D$ in $T$ with added vertex $s\in A_{1}$ or we ensure that $A_{1}\Rightarrow\{v_{0}\}$ . Henceforth we assume that $A_{1}\Rightarrow\{v_{0}\}$ .

The end of the proof is similar to the proof of Claim 3, with $v_{0}$ playing the role of $v_{-1}$ . Let $B_{1}^{\prime}=A_{1}$ and $B_{2}^{\prime}=N^{+}(v_{0})\cap A_{2}$ . We have $|B_{1}^{\prime}|=2n_{1}-1$ and, by (M2) on $\sigma_{0}$ , $|B_{2}^{\prime}|\geqslant n_{2}$ . Since $v_{-1},v_{-2n_{1}+1},\dots,v_{-1}$ is a directed cycle, in particular both $v_{-1}$ and $v_{-2}$ are the terminal vertices of a directed path of order $n_{1}$ in $B_{1}^{\prime}$ . Let ${O^{+}}^{\prime}$ be the set of vertices which are initial vertex of a directed path of order $n_{2}$ in $T\langle B_{2}^{\prime}\rangle$ . Note that ${O^{+}}^{\prime}\neq\emptyset$ because $|B_{2}^{\prime}|\geqslant n_{2}$ and, by Lemma 15, ${O^{+}}^{\prime}\Rightarrow(B_{2}\setminus{O^{+}}^{\prime})$ . Let $v_{k^{+}}$ be the vertex in ${O^{+}}^{\prime}$ with smallest index. Let $R^{-}$ be the directed path $v_{-n_{1}},\dots,v_{-1}$ and $R^{+}$ be a directed path of order $n_{2}$ in $T\langle B_{2}\rangle$ starting on $v_{k^{+}}$ .

We may assume that $v_{k^{+}}\rightarrow v_{-1}$ , for otherwise $v_{0}$ , $R^{-}$ , $R^{+}$ , the arcs between those paths and $v_{0}$ , and $v_{-1}v_{k^{+}}$ is a copy of $D$ in $T$ . If there is a vertex $v_{\ell}$ in $\{v_{1},\dots,v_{k^{+}-1}\}$ such that $v_{-1}\rightarrow v_{\ell}\rightarrow v_{k^{+}}$ , then by removing either the end-vertex of $R^{+}$ or the initial vertex of $R^{-}$ , we get that the union of $v_{0}$ , $R^{-}$ , $R^{+}$ and the arcs between those paths and $v_{0}$ is a copy of $D$ in $T$ . This holds because $v_{\ell}\notin B_{2}^{\prime}$ by choice of $v_{k^{+}}$ and $R^{+}$ is a directed path in $B_{2}^{\prime}$ . Henceforth, we assume that there is no such $v_{\ell}$ . Therefore, by (M4) and (M5) applied on $\sigma_{0}$ , $\hat{\sigma}=(v_{-2n_{1}+1},\dots,v_{-2},v_{k^{+}},v_{-1},\dots,v_{k^{+}-1},v_{k^{+}+1},\ldots,v_{2n_{2}-1})$ is a median order of $T$ . In particular, $v_{-2}\rightarrow v_{k^{+}}$ . Let ${R^{-}}^{\prime}$ be $v_{-n_{1}-1},\dots,v_{-2}$ . We thus obtain that the union of $v_{0}$ , ${R^{-}}^{\prime}$ , $R^{+}$ and the arcs between those paths and $v_{0}$ is a copy of $D$ in $T$ . ∎

References

[1] B. Alspach and M. Rosenfeld. Realization of certain generalized paths in tournaments. Discrete Mathematics, 34(2):199–202, 1981.
[2] J. Bang-Jensen and G. Gutin, editors. Classes of directed graphs. Springer monographs in mathematics. Springer International Publishing, Cham, Switzerland, 1st edition, July 2018.
[3] M. Bucić, S. Letzter, and B. Sudakov. Directed ramsey number for trees. Journal of Combinatorial Theory, Series B, 137:145–177, 2019. arXiv:1708.04504.
[4] L. N. Coregliano and A. A. Razborov. On the density of transitive tournaments. Journal of Graph Theory, 85(1):12--21, 2017. arXiv:1501.04074.
[5] N. Draganić, F. Dross, J. Fox, A. Girão, F. Havet, D. Korándi, W. Lochet, D. M. Correia, A. Scott, and B. Sudakov. Powers of paths in tournaments. Combinatorics, Probability and Computing, 30(6):894--898, 2021. arXiv:2010.05735.
[6] F. Dross and F. Havet. On the unavoidability of oriented trees. Journal of Combinatorial Theory, Series B, 151:83--110, 2021. arXiv:1812.05167.
[7] A. El Sahili. Trees in tournaments. Journal of Combinatorial Theory, Series B, 92(1):183--187, 2004.
[8] P. Erdős and L. Moser. On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125--132, 1964.
[9] R. Forcade. Parity of paths and circuits in tournaments. Discrete Mathematics, 6(2):115--118, 1973.
[10] J. Fox, X. He, and Y. Wigderson. Ramsey numbers of sparse digraphs. Israel Journal of Mathematics, 2024. arXiv:2105.02383.
[11] B. Grünbaum. Antidirected hamiltonian paths in tournaments. Journal of Combinatorial Theory, Series B, 11(3):249--257, 1971.
[12] R. Häggkvist and A. Thomason. Trees in tournaments. Combinatorica, 11(2):123–130, June 1991.
[13] F. Havet. Trees in tournaments. Discrete Mathematics, 243(1):121--134, 2002.
[14] F. Havet and S. Thomassé. Median orders of tournaments: a tool for the second neighborhood problem and Sumner’s conjecture. Journal of Graph Theory, 35(4):244--256, 2000.
[15] F. Havet and S. Thomassé. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld’s conjecture. Journal of Combinatorial Theory, Series B, 78(2):243--273, 2000.
[16] D. Kühn, R. Mycroft, and D. Osthus. An approximate version of Sumner’s universal tournament conjecture. Journal of Combinatorial Theory, Series B, 101(6):415--447, 2011. arXiv:1010.4429.
[17] T. Kóvari, V. T. Sós, and P. Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicum, 3(1):50–57, 1954.
[18] C. Lee. Ramsey numbers of degenerate graphs. Annals of Mathematics, 185(3), 2017. arXiv:1505.04773.
[19] N. Linial, M. Saks, and V. T. Sós. Largest digraphs contained in alln-tournaments. Combinatorica, 3(1):101--104, 1983.
[20] F. P. Ramsey. On a problem of formal logic. In Classic Papers in Combinatorics, pages 1--24. Springer, 1987.
[21] L. Rédei. Ein kombinatorischer Satz. Acta Litteraria Szeged, 7:39--43, 1934.
[22] K. Reid and E. Parker. Disproof of a conjecture of Erdös and Moser on tournaments. Journal of Combinatorial Theory, 9(3):225 -- 238, 1970.
[23] K. B. Reid and N. C. Wormald. Embedding oriented $n$ -trees in tournaments. Studia Scientiarum Mathematicarum Hungarica, 18(2-4):377--387, 1983.
[24] M. Rosenfeld. Antidirected Hamiltonian paths in tournaments. Journal of Combinatorial Theory, Series B, 12(1):93–99, Feb. 1972.
[25] A. Sanchez-Flores. On tournaments free of large transitive subtournaments. Graphs and Combinatorics, 14(2):181--200, Jun 1998.
[26] H. J. Straight. The existence of certain type of semi-walks in tournaments. Congressus Numerantium, 29:901--908, 1980.
[27] A. Thomason. Paths and cycles in tournaments. Transactions of the American Mathematical Society, 296(1):167--180, 1986.

	$\displaystyle\|\{i,\dots,2q\|V(F_{j})\|\}\cap\{\iota(x)\mid x\in V(F_{j})\}\|$	$\displaystyle\leqslant\frac{1}{q}\left(2q\|V(F_{j})\|-i+1\right),$
	$\displaystyle\text{and~{}~{}~{}~{}}\|\{-2q\|V(F_{j})\|,\dots,i\}\cap\{\iota(x)\mid x\in V(F_{j})\}\|$	$\displaystyle\leqslant\frac{1}{q}\left(i+2q\|V(F_{j})\|+1\right).$

Blow-ups and extensions of trees in tournaments

Abstract

1 Introduction

Proposition 1.

Proposition 2.

Proof.

Theorem 3 (Rédei [21]).

Conjecture 4 (Sumner).

Theorem 5 (Kühn, Mycroft, and Osthus [16]).

Problem 6.

Our results

Conjecture 7.

Problem 8.

Conjecture 9.

Conjecture 10.

Conjecture 11.

Problem 12.

2 Preliminaries

2.1 Basic properties of tournaments

Lemma 13 ([2, Proposition 2.2.2]).

Lemma 14 ([2, Proposition 2.7.6]).

Lemma 15.

Proof.

2.2 Median order

Lemma 16.

Proof.

2.3 A Kővári-Sós-Turán-like lemma

Lemma 17.

Proof.

3 Blow-ups of oriented trees

Theorem 18.

Proof.

Claim 1.

Claim 2.

4 Extensions of oriented trees

Lemma 19 (Folklore).

Proof.

Lemma 20 (Folklore).

Proof.

Theorem 21.

Corollary 22.

Proof of Theorem 21.

Lemma 23.

Proof.

Theorem 24.

Corollary 25.

Proof of Theorem 24.

5 Particular extensions of some particular forests

5.1 Twin extensions of arcless digraphs

Proposition 26.

Proof.

Proposition 27 (Chernoff’s Bound).

Proposition 28.

Proof.

Theorem 29 (Ramsey’s theorem [20]).

Theorem 30.

Proof.

5.2 11-extensions of directed paths

Theorem 31.

Proof.

Claim 3.

References

5.2 $1$ -extensions of directed paths