= Solution
Both alternatives can be proved. For the <oriented tree> alternative take $n\ge2$; at $n=1$ the displayed <tournament> order is zero, so that unqualified boundary case cannot be intended.
Choose a <median order of a tournament> $v_1,\ldots,v_N$, maximizing its number of forward <directed edges>. Every interval inherits a <median order>, since improving that interval would improve the whole order. If $v_i$ had fewer outneighbours than inneighbours in $v_{i+1},\ldots,v_j$, moving it just past $v_j$ would increase the number of forward <directed edges>. Hence it has at least half the <vertices> of that later interval as outneighbours.
Call a <graph embedding> half-sparse if every proper final interval $I$ satisfies $|f(T)\cap I|<|I|/2+1$. This <half-sparse median-order embedding> admits a useful extension. Suppose an outward leaf is attached to a vertex mapped to $v_i$, and reserve two extra <vertices> at the end of the <tournament> order. In the old interval after $v_i$, half-sparsity bounds the number of occupied <vertices> by less than half its size plus one. The interval extended by two <vertices> has at least that half-size plus one outneighbours of $v_i$. Thus at least one outneighbour is free; map the new leaf there. Every old final interval has gained two available places and at most one new image, so its strict inequality persists. Final intervals wholly within the two new places contain at most one image, so they also satisfy the inequality. This proves the extension, not just an existence assertion about degrees.
Starting with an <directed edge> in a two-vertex <tournament> and repeatedly attaching outward leaves proves that every $h$-vertex <arborescence> embeds half-sparsely in every $(2h-2)$-vertex <tournament> for $h\ge2$. The root-first construction supplies the induction. An unused suffix can be appended without destroying the inequality; for a suffix which contains the whole old order the extra place supplies the needed strictness. A singleton embeds half-sparsely in the first vertex of a two-vertex order. Reversing the <oriented tree> and <tournament> gives ordinary embeddings of reversed <arborescences> in $2h-2$ <vertices> as well.
Here is the stronger invariant needed for an arbitrary <oriented tree>. Root it at a source. Classify each <directed edge> as forward or backward according to whether it points away from or towards the root in the underlying <rooted tree>. Let $b$ be the number of backward <directed edges> and $c$ the number of nonempty connected components made of these <directed edges>, ignoring isolated <vertices>. Put $d=b-c$. We claim that the <oriented tree> has a <half-sparse embedding> in every median-ordered <tournament> of order $2n+2d$.
Induct on the <oriented tree> order. If it has a forward leaf, delete that leaf, use the induction hypothesis and apply the two-place extension. Neither $b$ nor $c$ changes. If there are no backward <directed edges>, use the <arborescence> construction. Otherwise first remove forward leaves as above, so every remaining leaf is backward. Choose a backward component furthest from the root. It must be a pendant subtree: a forward continuation below it would either reach another backward component, contrary to its choice, or end at a forward leaf. Let this component have $h\ge2$ <vertices> and top vertex $y$. Since the root is a source, $y$ is not the root; its joining <directed edge> from its parent $x$ is forward. The component is an reversed <arborescence> rooted at $y$.
Delete the component. The remaining <oriented tree> has parameters
$$
n'=n-h,\qquad b'=b-h+1,\qquad c'=c-1,\qquad d'=d-h+2.
$$
Its required <tournament> order is $2n+2d-4h+4$. Embed it in the initial interval of this length. Temporarily attach $2h-2$ outward leaves at $x$, using the extension lemma repeatedly. This consumes exactly $4h-4$ extra places and gives a <half-sparse embedding> of the enlarged <oriented tree> in the original <tournament>. The $2h-2$ temporary images all lie in the outneighbourhood of $f(x)$; among them embed the deleted reversed <arborescence>. Its root automatically receives the joining <directed edge> from $f(x)$. Replace the temporary leaves by this component. The final image is a subset of the temporary enlarged image, so half-sparsity survives. This proves the invariant with the precise count, including the case when the remaining <oriented tree> is a singleton.
Unless the <oriented tree> is already an in- or out-arborescence, every rooting has at least one backward component. Choose one orientation, reversing all <directed edges> if necessary, so that some rooting has at most $(n-1)/2$ backward <directed edges>. It then has $d\le(n-3)/2$. Within this fixed orientation choose the root to minimize $(d,b)$ lexicographically. If a neighbour pointed into the root, move the root across that <directed edge>. Only this <directed edge> changes its forward/backward classification. Removing it from the backward forest decreases $b$ by one and decreases $c$ by at most one; hence it cannot increase $d$, and when $d$ stays equal it strictly decreases $b$. This contradicts the chosen minimum. Thus the chosen root is a source, while its $d$ retains the required bound. Reversal does not affect a universal tournament-embedding assertion, because one reverses the host <tournament> too. The invariant proves the <three-times-order tournament bound for oriented trees>:
$$
\boxed{T\subseteq R\quad\text{whenever }|T|=n\ge2,\ |R|=3n-3.}
$$
For the lower obstruction, take the outward <graph star> with $n-1$ leaves. There is a <regular tournament> on $2n-3$ <vertices>: on residues modulo $2n-3$, direct $i\to j$ when $j-i$ is one of $1,\ldots,n-2$. Every vertex has outdegree $n-2$, so none can be the centre of that outward star. Thus \b[the universal bound cannot be reduced to $2n-3$].
For the <strongly connected directed graph> alternative, the correct universal assertion is an upper bound by the <independence number>, together with examples needing that many <directed circuits>. The literal assertion that every such <graph> needs $\alpha(D)$ <directed circuits> is false: a directed four-cycle has <independence number> two and is spanned by one <directed circuit>. Work with a nontrivial strongly connected digraph; a loopless singleton has no <directed circuit>.
Use the permitted <coherent cyclic order of a digraph>. Representatives differ by cyclic rotations and swaps of consecutive nonadjacent <vertices>. In every representative, a backward <directed edge> $v_j\to v_i$ has a forward <directed path> from $v_i$ to $v_j$. A <directed circuit> with one backward <directed edge> winds once around the order. Every vertex belongs to such a <directed circuit>, because every vertex has an outgoing <directed edge> and coherence puts that <directed edge> on a once-winding <directed circuit>. Let $k$ be the <cyclic stability of a digraph order>: the largest size of an <independent set> consecutive in an equivalent order. Then $k\le\alpha(D)$.
We need a short ordering lemma. If a set $X$ has no forward path between distinct members, then $|X|\le k$. Among equivalent representatives retaining this property, minimize the span from its first to its last member. Suppose there is a vertex in a gap. If some gap vertex $y$ cannot be reached from an earlier member of $X$ by a forward path, take the first such $y$. Every preceding gap vertex in the span is reachable from an earlier member of $X$. It follows that $y$ has no forward incoming <directed edge> from anywhere in that part of the span; a backward outgoing <directed edge> to it is also impossible, since coherence would supply the same forbidden forward reachability. Thus $y$ is nonadjacent to every intervening vertex and can be moved before the first member of $X$, shortening the span. Otherwise every gap vertex is reachable from an earlier member of $X$. Take the last one. It cannot have a forward path to a later member of $X$, and coherence consequently rules out <directed edges> in either direction to the following members of $X$. Move it past them, again shortening the span. Swaps of nonadjacent <vertices> do not change the forward-edge <graph>, so these moves preserve the hypothesis. Both cases contradict minimality. Therefore $X$ is consecutive. It is independent: a forward <directed edge> is forbidden by hypothesis, and a backward <directed edge> would imply a forward path by coherence. Rotate it to the start to obtain $|X|\le k$.
Choose a representative starting with a stable block $S=\{s_1,\ldots,s_k\}$. Add sink copies $s'_1,\ldots,s'_k$, retain all forward <directed edges> of $D$, and add $v\to s'_i$ for each original <directed edge> $v\to s_i$. This is an acyclic auxiliary <directed graph> $A$. A once-winding <directed circuit> through $s_i$ cannot visit another block member, since no forward path can join two members of this initial independent block. Opening this <directed circuit> gives a path from $s_i$ to $s'_i$ in $A$.
The <partial order> defined by reachability in $A$ has width exactly $k$. The sink copies already form an <antichain> of size $k$. For the reverse inequality, let $X$ be an <antichain> and let $J$ index its sink copies. Permute the independent initial block so that these labels come first, then rotate that part of the block to the end. The set
$$
Y=(X\cap V(D))\cup\{s_j:j\in J\}
$$
has size $|X|$: a vertex and its own copy cannot both belong to $X$, since they are comparable by the opened <directed circuit>. There is no forward path between distinct members of $Y$ in the rotated order. A path between original members would give comparability in $A$; a path from an original member to $s_j$ would become a path to its sink copy, also forbidden. No forward path leaves the final stable block. The ordering lemma therefore gives $|X|=|Y|\le k$.
Apply the <Dilworth theorem> to partition this reachability order into $k$ <chains in a partial order>. Each chain contains exactly one original block vertex and exactly one sink copy, since each of these two <antichains> has size $k$; these are its first and last elements. Expand consecutive chain relations into <directed paths> in $A$. The paths cover all <vertices>, though intervening <vertices> can occur on several paths. Label their heads $s_i$ and their tails $s'_{\sigma(i)}$; the tail labels define a <permutation> $\sigma$.
Among all such covering path families maximize the number of cycles of $\sigma$. If two paths whose labels lie in the same <permutation> cycle meet at a vertex, exchange their suffixes there. The paths remain simple, since the auxiliary <graph> is acyclic, and their union still covers the same <vertices>. Exchanging the two tail labels splits that <permutation> cycle into two, a contradiction. Thus paths in the same <permutation> cycle are disjoint. Identify every $s'_i$ with $s_i$ and concatenate the paths around each cycle of $\sigma$. Each concatenation is a genuine <directed circuit>, with no repeated vertex except its closing vertex. Together these <directed circuits> cover $D$, and there are at most $k\le\alpha(D)$ of them. This proves the <circuit-cover bound by independence number>:
$$
\boxed{D\text{ has a spanning circuit family of size at most }\alpha(D).}
$$
Finally, form $k$ directed triangles sharing just one central vertex, with no <directed edges> between their other <vertices>. This <strongly connected directed graph> has <independence number> $k$, by taking one outer vertex from each triangle. A simple <directed circuit> can use only one triangle, since visiting a second requires repeating the centre. Exactly $k$ <directed circuits> are therefore necessary. \b[The bound $\alpha(D)$ is sharp in general; $\alpha(D)-1$ is not a universal bound.]
Back to article page
