The Prescribed-Vertex Semidegree Threshold for Directed $3q$-Cycles in Oriented Graphs

Abstract.

For every $q\geq 2$, we prove that every oriented graph $G$ on $n\geq 45q-8$ vertices whose minimum semidegree satisfies

$$\delta^{0}(G)\geq\left\lceil\frac{n}{3}\right\rceil$$

contains a directed cycle of length $3q$ through every vertex. The semidegree bound is sharp. This closes the one-unit gap left by the prescribed-vertex theorem of Kelly, Kühn and Osthus when $3\mid n$. We also prove that if an oriented graph $H$ has order $N$, minimum semidegree $d\geq 3$, and $7d\geq 2N+3$, then every ordered pair of distinct vertices is joined by a path of length three, four, or five. The constant $+3$ is best possible. As a consequence, the order hypothesis $n\geq 10^{10}\ell$ in the general prescribed-vertex theorem of Kelly, Kühn and Osthus can be replaced by $n\geq 15\ell-60$ for $\ell\geq 7$.

1. Introduction

An oriented graph is an orientation of a simple graph. For a vertex $v$ of an oriented graph $G$, let $d^{+}(v)$ and $d^{-}(v)$ denote its outdegree and indegree. Denote

$$\delta^{\pm}(G)=\min_{v\in V(G)}d^{\pm}(v),\qquad\delta^{0}(G)=\min\{\delta^{+}(G),\delta^{-}(G)\}.$$

All paths and cycles in this paper are directed unless stated otherwise. We write $C_{\ell}$ for the consistently oriented cycle of length $\ell$.

Degree conditions for directed cycles in oriented graphs, and in particular for Hamilton cycles, are surveyed by Bermond and Thomassen [1] and by Kühn and Osthus [11]. We consider the minimum semidegree condition that forces a directed cycle of a given length through each specified vertex.

For $\ell\geq 3$, let $\tau^{v}_{\ell}(n)$ be the least integer $d$ such that every $n$-vertex oriented graph $G$ with $\delta^{0}(G)\geq d$ contains a copy of $C_{\ell}$ through every vertex. The superscript emphasizes that this is a prescribed-vertex, or vertex-rooted, threshold: it is stronger than merely requiring one copy of $C_{\ell}$ somewhere in the graph.

Kelly, Kühn and Osthus [10] proved that, for every $\ell\geq 4$ and every $n\geq 10^{10}\ell$, the condition

$$\delta^{0}(G)\geq\left\lfloor\frac{n}{3}\right\rfloor+1$$

forces a copy of $C_{\ell}$ through any prescribed vertex. When $3\mid\ell$, their modified cyclic blow-up [10] gives a prescribed vertex contained in no $C_{\ell}$ while

$$\delta^{0}(G)=\left\lfloor\frac{n-1}{3}\right\rfloor.$$

Consequently, for $\ell=3q\geq 6$ and $n\geq 10^{10}\ell$,

(1) $$\left\lceil\frac{n}{3}\right\rceil\leq\tau^{v}_{3q}(n)\leq\left\lfloor\frac{n}{3}\right\rfloor+1.$$

The two bounds coincide when $n\equiv 1,2\pmod{3}$. For $n=3m$, however, they leave precisely the one-unit window

$$m\leq\tau^{v}_{3q}(3m)\leq m+1.$$

Denote

(2) $$n_{0}(q)=\begin{cases}37,&if~q=2,\\ 97,&if~q=3,\\ 45q-8,&if~q\geq 4.\end{cases}$$

We present the main results as follows.

Theorem 1.1.

Let $q\geq 2$ and $n\geq n_{0}(q)$. If $G$ is an oriented graph on $n$ vertices and

$$\delta^{0}(G)\geq\left\lceil\frac{n}{3}\right\rceil,$$

then every vertex of $G$ lies on a copy of $C_{3q}$.

Corollary 1.2.

For every $q\geq 2$ and $n\geq n_{0}(q)$,

$$\tau^{v}_{3q}(n)=\left\lceil\frac{n}{3}\right\rceil.$$

For $3\mid n$ and $n\geq n_{0}(q)$, this replaces the upper bound $m+1$ in (1) by $m$.

The order bound in Theorem 1.1 follows from a three-length linking lemma. With $\ell=3q$, the hypothesis $n\geq n_{0}(q)$ is $n\geq 15\ell-8$ for $q\geq 4$, in place of $n\geq 10^{10}\ell$. If an oriented graph $H$ has order $N$ and minimum semidegree $d\geq 3$, then

$$7d\geq 2N+3$$

guarantees, between every ordered pair of distinct vertices, a path of length three, four, or five. We give examples with $7d=2N+2$, so the additive constant is sharp. In the defect parameterization $d\geq N/3-C+1$, where $C$ is a positive integer, the lemma already applies when $N\geq 21C-12$. The coefficient $21$ is asymptotically best possible.

Jackson [6] gave classical semidegree conditions for long directed paths and cycles. Darbinyan and Karapetyan [3] studied short paths, including versions with forbidden vertices. Their result bounds directed distance but does not guarantee a path whose length belongs to $\{3,4,5\}$. Zhou and Yan [14] proved an $H$-linkage theorem at the $3n/8$ scale for fixed $H$, sufficiently large order, and prescribed subdivision-path lengths at least four. Its semidegree condition is above the one-third scale considered here.

The same short-linking lemma improves the large-order hypothesis in the full prescribed-vertex theorem of Kelly, Kühn and Osthus, without the restriction $3\mid\ell$. We prove below that, for every $\ell\geq 7$, the condition

$$n\geq 15\ell-60,\qquad\delta^{0}(G)\geq\left\lfloor\frac{n}{3}\right\rfloor+1$$

forces a copy of $C_{\ell}$ through every prescribed vertex. Their direct arguments for $\ell=4,5,6$ already require only $n\geq\ell$. Thus the same theorem has an explicit linear order bound for every length. To the best of our knowledge, no previous result improves the explicit condition $n\geq 10^{10}\ell$ while retaining both the prescribed vertex and the assumption $\delta^{0}(G)\geq\lfloor n/3\rfloor+1$. For $\ell=3q$ and $n=3m$, this corollary still assumes $\delta^{0}(G)\geq m+1$. The equality analysis lowers this to $m$; the deletion budgets for $q=2$, $q=3$, and $q\geq 4$ give the three values in (2). If $q\geq 3$ and $3\nmid n$, Corollary 2.8 gives the stronger order bound $n\geq 45q-60$.

Without prescribing a vertex, Czygrinow, Molla, Nagle and Oursler [2] proved that, for each fixed $\ell\geq 4$ and all sufficiently large $n$, the one-sided condition

$$\delta^{+}(G)\geq\frac{n+1}{3}$$

forces a copy of $C_{\ell}$. Their theorem does not give a rooted conclusion or an explicit order bound.

The $3n/8$ Hamiltonian threshold was developed in [5, 9] and determined exactly for large order in [8]. At this denser scale, Kelly, Kühn and Osthus [10] proved that every prescribed vertex lies on a directed cycle of every length $4\leq\ell\leq n$, while Wang, Wang and Zhang [13] treat arbitrary orientations without a prescribed vertex. These results do not apply at semidegree $n/3$.

The restriction $q\geq 2$ is essential. A directed triangle through a prescribed vertex has a different threshold: Kelly, Kühn and Osthus [10] showed that its asymptotic scale is $2n/5$, rather than $n/3$. Thus $C_{3}$ does not belong to the phenomenon studied here.

The rooted problem is different from ordinary, unrooted containment. Kelly, Kühn and Osthus [10, Conjecture 5] conjectured that, if $\ell\geq 4$ and $k>2$ is the smallest integer that does not divide $\ell$, then, for all sufficiently large $n$, the condition

$$\delta^{0}(G)\geq\left\lfloor\frac{n}{k}\right\rfloor+1$$

forces a copy of $C_{\ell}$ in every oriented graph $G$ on $n$ vertices. The conjectured threshold is suggested by cyclic blow-ups. For $k\geq 7$ and $\ell\geq 10^{7}k^{6}$, Kühn, Osthus and Piguet [12] proved the corresponding asymptotic result: for every $\eta>0$, the condition $\delta^{0}(G)\geq(1+\eta)n/k$ suffices for all sufficiently large $n$. Grzesik and Volec [4, Theorem 1.4] later determined the corrected exact thresholds for this unrooted problem. The conjectured bound is exact when $3\nmid\ell$ or $\ell\equiv 3\pmod{12}$; the other congruence classes require the rounding corrections stated in their theorem. In particular, when $3\mid\ell$ and $\ell\neq 3$, one has $k\geq 4$, so the unrooted threshold is at most $n/4+O(1)$. Requiring the cycle to pass through an arbitrary vertex restores the one-third barrier, as the lower construction behind (1) shows. Related prescribed-vertex results under the additional assumption that the oriented graph contains no directed triangle were obtained by Ji, Wu and Song [7, Theorem 1.4].

Only the case $n=3m$ requires an additional argument. Fix the prescribed vertex $x$. If $N^{+}(x)$ is independent, Lemma 2.9 gives the root-dominating balanced cut. Otherwise choose an arc $h\to z$ in $G[N^{+}(x)]$. If $N^{+}(z)$ is independent, the same lemma gives the transitive-entry balanced cut; if not, an arc in $G[N^{+}(z)]$ produces an $xy$-butterfly. In the two balanced-cut cases, the row-family classification and matching arguments are used in Propositions 4.2 and 5.1. The butterfly case is completed by Lemmas 6.1 and 6.2. When $3\nmid n$, every outneighbourhood is non-independent at the threshold $\delta^{0}(G)\geq\lceil n/3\rceil$, so only the butterfly case is needed. Sections 2–6 follow this order.

2. Short linking and preliminary reductions

For an oriented graph $G$, write $V(G)$ for its vertex set and $|G|=|V(G)|$ for its order. For $v\in V(G)$, let $N_{G}^{+}(v)$ and $N_{G}^{-}(v)$ be its out- and inneighbourhoods, and put $d_{G}^{\pm}(v)=|N_{G}^{\pm}(v)|$. We omit the subscript $G$ when the ambient graph is clear. For $X\subseteq V(G)$, define

$$N^{\pm}(X)=\bigcup_{x\in X}N^{\pm}(x).$$

Thus the external neighbourhood of $X$ is $N^{\pm}(X)\setminus X$. For $Y\subseteq V(G)$, set

$$N_{Y}^{\pm}(v)=N^{\pm}(v)\cap Y,\qquad d_{Y}^{\pm}(v)=|N_{Y}^{\pm}(v)|.$$

We write $G[X]$ for the subgraph induced by $X$, $e(X)$ for its number of arcs, and, for disjoint sets $X,Y$, $e(X,Y)$ for the number of arcs directed from $X$ to $Y$. A vertex string $v_{0}v_{1}\cdots v_{k}$ denotes the directed path

$$v_{0}\to v_{1}\to\cdots\to v_{k}.$$

We use the following two elementary facts repeatedly.

Lemma 2.1.

Let $G$ be an oriented graph.

1. Every nonempty $X\subseteq V(G)$ satisfies $e(X)\leq\binom{|X|}{2}$. Consequently,

   $$|N^{+}(X)\setminus X|\geq\delta^{+}(G)-\frac{|X|-1}{2},$$

   and the analogous reverse inequality holds for $N^{-}(X)\setminus X$.

2. Every independent set has size at most $|G|-2\delta^{0}(G)$.

Proof.

The first assertion follows because an oriented graph has at most one arc on each unordered pair. Choose a vertex of $G[X]$ with outdegree at most $(|X|-1)/2$ to obtain the displayed inequality; reverse all arcs for its counterpart. If $X$ is independent, then for any $x\in X$ the sets $N^{+}(x)$ and $N^{-}(x)$ are disjoint subsets of $V(G)\setminus X$, giving $|G|-|X|\geq 2\delta^{0}(G)$. ∎

Kelly, Kühn and Osthus [10] proved that, for a positive integer $C$, under the hypotheses

$$\delta^{0}(H)\geq N/3-C+1\qquad\text{and}\qquad N\geq 8\cdot 10^{9}C,$$

every ordered pair of distinct vertices is joined by a path whose length belongs to $\{3,4,5\}$. The next lemma replaces their large-order hypothesis by a sharp linear inequality.

Lemma 2.2.

Let $H$ be an oriented graph of order $N$, and put $d=\delta^{0}(H)$. If $d\geq 3$ and

$$7d\geq 2N+3,$$

then every ordered pair of distinct vertices $x,y$ is joined by an $x$–$y$ path of length $3$, $4$, or $5$.

Proof.

The proof idea has three steps. We first choose equal-sized sets in the outneighbourhood of the initial vertex and the inneighbourhood of the terminal vertex; the absence of paths of lengths $3$, $4$, and $5$ then forces a rigid system of forbidden arcs between the resulting layers. Minimum semidegree makes two intermediate layers large, while the forbidden arcs give an incompatible upper bound on the total outdegree of one of them. The contradiction reduces to a quadratic inequality. Its two endpoint estimates use precisely the relation $7d\geq 2N+3$.

Step 1: the forbidden-arc structure. Put $s=d-2$. The sets $N^{+}(x)\setminus\{y\}$ and $N^{-}(y)\setminus\{x\}$ both have size at least $s+1$. Choose an $s$-set $X\subseteq N^{+}(x)\setminus\{y\}$. Since $|N^{-}(y)\setminus\{x\}|\geq s+1>|X|$, there is an $s$-set $Y\subseteq N^{-}(y)\setminus\{x\}$ with $Y\neq X$. Set

$$Z=X\cap Y,\qquad A=X\setminus Y,\qquad B=Y\setminus X,\qquad a=|A|=|B|\geq 1.$$

Suppose, for a contradiction, that there is no $x$–$y$ path of length $3$, $4$, or $5$. Then there is no arc from $X$ to $Y$. Define

$$P=N^{+}(A)\setminus(X\cup\{x,y\}),\qquad Q=N^{-}(B)\setminus(Y\cup\{x,y\}),$$

and put $p=|P|$ and $u=|Q|$. The sets $X\cup Y$, $P$, $Q$, and $\{x,y\}$ are pairwise disjoint. Indeed, $P\cap Y\neq\varnothing$ or $Q\cap X\neq\varnothing$ would give an $x$–$y$ path of length three, while $P\cap Q\neq\varnothing$ would give one of length four. We also have

$$P\nrightarrow Y,\qquad P\nrightarrow Q,\qquad P\nrightarrow y;$$

otherwise there is an $x$–$y$ path of length four, five, or three, respectively.

Step 2: degree counting. Let

$$R=V(H)\setminus\bigl((X\cup Y)\cup P\cup Q\cup\{x,y\}\bigr),\qquad\rho=|R|=N-d-a-p-u,$$

and define

$$L=d-\frac{a+1}{2}.$$

Since $a\leq s=d-2$, we have $L\geq(d+1)/2>0$. No arc goes from $A$ to $Y$, and $A\nrightarrow x$ because $x\to A$. Hence every out-arc of $A$ goes inside $A$, to $P$, or possibly to $y$, and therefore

$$e(A,P)\geq ad-\binom{a}{2}-a=aL.$$

The reverse argument, applied to the indegrees of $B$, gives $e(Q,B)\geq aL$. Consequently,

$$p,u\geq L.$$

All out-arcs of $P$ go to $A$, inside $P$, to $R$, or possibly to $x$. Orientedness between $A$ and $P$ gives $e(P,A)\leq ap-e(A,P)\leq ap-aL$. Summing the outdegrees of the vertices of $P$, we obtain

$$pd \leq e(P,A)+e(P)+e(P,R)+e(P,\{x\})$$

$$\leq ap-aL+\binom{p}{2}+p\rho+p.$$

Thus

$$0\geq F:=p\left(d-a-\rho-\frac{p+1}{2}\right)+aL.$$

Substituting the value of $\rho$ and using $u\geq L$ gives

$$F\geq\frac{p^{2}}{2}-p\left(\frac{a}{2}+c\right)+aL=:h(p,a),\qquad c:=N-3d+1.$$

The hypothesis $7d\geq 2N+3$ is equivalent to

(3) $$d\geq 2c+1.$$

Step 3: the quadratic contradiction. Write $\kappa=a/2+c$. If $L\geq\kappa$, then $h$ is increasing in $p$ for $p\geq L$, and

$$h(p,a)\geq h(L,a)=L\left(\frac{L+a}{2}-c\right)>0.$$

Indeed, $L+a=d+(a-1)/2\geq d$, so the last factor is at least $d/2-c\geq 1/2$ by (3).

It remains that $L<\kappa$. For fixed $a$, the convex quadratic $h(p,a)$ is minimized at $p=\kappa$, so

$$h(p,a)\geq g(a):=a\left(d-\frac{a+1}{2}\right)-\frac{1}{2}\left(\frac{a}{2}+c\right)^{2}.$$

Since $a$ is an integer, $L<\kappa$ is equivalent to $a\geq d-c$. Together with $a\leq d-2$, this implies $c\geq 2$. The function $g$ is concave in $a$, so it suffices to check the two endpoints of

$$d-c\leq a\leq d-2.$$

Write $t=d-2c-1\geq 0$. Direct expansion gives

$$8g(d-c) =3c^{2}+6c-1+(10c+2)t+3t^{2}>0,$$

$$8g(d-2) =16c-9+(8c+6)t+3t^{2}>0.$$

Thus $g(a)>0$ throughout the interval, again contradicting $F\leq 0$. ∎

Substituting $d\geq N/3-C+1$ in Lemma 2.2 gives the following form.

Corollary 2.3.

Let $C$ be a positive integer. If $H$ is an oriented graph on $N\geq 21C-12$ vertices with

$$\delta^{0}(H)\geq\frac{N}{3}-C+1,$$

then every ordered pair of distinct vertices is joined by a path of length $3$, $4$, or $5$.

Proof.

Put $d=\delta^{0}(H)$. The hypotheses give

$$d\geq\frac{N}{3}-C+1\geq 6C-3\geq 3$$

and

$$7d\geq 7\left(\frac{N}{3}-C+1\right)\geq 2N+3.$$

Apply Lemma 2.2. ∎

The following construction shows that $+3$ cannot be reduced and that the coefficient $21$ is asymptotically best possible.

Proposition 2.4.

For every integer $c\geq 2$, there is an oriented graph $H_{c}$ of order $N=7c-1$ with $\delta^{0}(H_{c})=2c$ and vertices $x,y$ such that no $x$–$y$ path has length $3$, $4$, or $5$. Thus the constant $+3$ in Lemma 2.2 cannot be replaced by $+2$. Moreover, the coefficient $21$ in Corollary 2.3 is asymptotically best possible.

Proof.

Take disjoint sets $S,P,Q,R$ with

$$|S|=|P|=|Q|=2c-1,\qquad|R|=c,$$

together with two vertices $x,y$. Let $P$ and $Q$ induce regular tournaments, and let $S$ and $R$ be independent. Add all arcs indicated by

$$x\to y,\qquad x\to S\to y,$$

$$S\to P\to R\to Q\to S,$$

and

$$y\to P\cup Q\cup R,\qquad P\cup Q\cup R\to x,$$

with no other arcs between the parts. Regular tournaments exist on $2c-1$ vertices.

The vertices in $\{x\}$, $\{y\}$, $S$, $P$, $Q$, and $R$ have respective $(d^{-},d^{+})$-pairs

$$(5c-2,2c),\quad(2c,5c-2),\quad(2c,2c),\quad(3c-1,2c),\quad(2c,3c-1),\quad(2c,2c).$$

Hence $|H_{c}|=7c-1$ and $\delta^{0}(H_{c})=2c$, so

$$7\delta^{0}(H_{c})=14c=2|H_{c}|+2.$$

Every $x$–$y$ path is either the arc $xy$, has the form $xsy$ with $s\in S$, or begins $x\to S\to P$. In the last case, any simple path ending at $y$ must pass successively through

$$P,\ R,\ Q,\ S,\ y;$$

arcs inside the regular tournaments can only increase its length. Thus every remaining $x$–$y$ path has length at least six.

Set

$$C_{c}=\left\lceil\frac{c+2}{3}\right\rceil.$$

Then $2c\geq(7c-1)/3-C_{c}+1$, while $(7c-1)/C_{c}\to 21$. Consequently, there are no constants $\gamma<21$ and $K$ for which the condition $N\geq\gamma C+K$ is a universal sufficient order hypothesis in Corollary 2.3. ∎

We next record the extension and deletion statements used below.

Lemma 2.5.

Let $G$ be an oriented graph.

1. Let $d$ and $L$ be nonnegative integers. If $\delta^{+}(G)\geq d$, $F\subseteq V(G)$, $v\notin F$, and

   $$|F|+L\leq d,$$

   then $G$ contains a simple path of length $L$ starting at $v$ and otherwise avoiding $F$.

2. Let $G$ have order $n$ and minimum semidegree at least $\lceil n/3\rceil$, and let $R\geq 0$ be an integer. If

   $$n\geq 15R+7$$

   and $H$ is obtained by deleting at most $R$ vertices, then every ordered pair of distinct vertices of $H$ is joined in $H$ by a path of length $3$, $4$, or $5$.

3. Let $G$ have order $n$ and minimum semidegree at least $\lceil n/3\rceil$. Let $\ell$ and $B$ be integers with $\ell\geq B\geq 6$, let $x,a$ be distinct vertices, and let $Z\subseteq V(G)\setminus\{x,a\}$. Suppose that, for each $j\in\{B-5,B-4,B-3\}$, there is an $x$–$a$ path $Q_{j}$ of length $j$ whose internal vertices lie in $Z$. Put

   $$R=|Z|+\ell-B.$$

   If

   $$|Z|+1+\ell-B\leq\left\lceil\frac{n}{3}\right\rceil\qquad\text{and}\qquad n\geq 15R+7,$$

   then $x$ lies on a copy of $C_{\ell}$.

Proof.

For (i), extend greedily. Before the $(j+1)$st step, at most $|F|+j$ vertices are forbidden, which is smaller than $d$ for $0\leq j<L$.

For (ii), let $r\leq R$ vertices be deleted, put $N=|H|=n-r$, and write $n=3m+s$ with $s\in\{0,1,2\}$. Set

$$D=\left\lceil\frac{n}{3}\right\rceil=\begin{cases}m,&s=0,\\ m+1,&s=1,2.\end{cases}$$

Then $\delta^{0}(H)\geq D-r$. A direct calculation shows that

(4) $$7(D-r)-\bigl(2(n-r)+3\bigr)=\begin{cases}m-5r-3,&s=0,\\ m-5r+2,&s=1,\\ m-5r,&s=2.\end{cases}$$

The hypothesis $n\geq 15R+7$ gives

$$m\geq\begin{cases}5R+3,&s=0,\\ 5R+2,&s=1,2.\end{cases}$$

Since $r\leq R$, the three expressions in (4) are respectively at least $0$, $4$, and $2$. Moreover, $D-r\geq D-R\geq 4R+3\geq 3$. Lemma 2.2 now applies to $H$.

For (iii), apply (i) with forbidden set $Z\cup\{x\}$ to obtain a path $P$ of length $\ell-B$ from $a$ to a vertex $y$. Delete $Z$ and $V(P)\setminus\{y\}$. At most $R$ vertices are deleted, so (ii) gives a $y$–$x$ path of some length $t\in\{3,4,5\}$. The paths $Q_{B-t}$, $P$, and the $y$–$x$ path are internally disjoint and together form a $C_{\ell}$. ∎

Remark 2.6.

The three cases in (2) come from three different deletion budgets. For $q=2$, the only critical use of short linking deletes $R=\ell-4=2$ vertices in the transitive-entry branch, giving $15R+7=37$. For $q=3$, a terminal-safe three-chain is already a $C_{9}$; the largest remaining budget is $R=\ell-3=6$ in the distinct-row subcase of the transitive-entry branch, giving $15R+7=97$. For $q\geq 4$, the terminal-safe-chain branch of Proposition 4.2 may delete $R=\ell-1=3q-1$ vertices, giving $15R+7=45q-8$. These are the smallest uniform cutoffs delivered by the present argument. The stable balanced-cut branches use only the matching inequality $m\geq 2q+11$.

Following Kelly, Kühn and Osthus  [10, discussion preceding Fact 18], an $xy$-butterfly consists of five distinct vertices $x,h,z,b,y$ and the six arcs

$$xh,\ xz,\ hz,\ zb,\ zy,\ by.$$

It contains $x$–$y$ paths of lengths $2$, $3$, and $4$.

The sharp linking lemma also gives a linear order bound in the full prescribed-vertex theorem of Kelly, Kühn and Osthus.

Corollary 2.7.

Let $\ell\geq 7$ and $n\geq 15\ell-60$. If $G$ is an oriented graph on $n$ vertices with

$$\delta^{0}(G)\geq\left\lfloor\frac{n}{3}\right\rfloor+1,$$

then every vertex of $G$ lies on a copy of $C_{\ell}$.

Proof.

Fix $x\in V(G)$ and put $D=\lfloor n/3\rfloor+1$. By Lemma 2.1(ii), every independent set has size at most $n-2D<D$. Hence $N^{+}(x)$ contains an arc $h\to z$, and $N^{+}(z)$ contains an arc $b\to y$. The five vertices are distinct, and

$$xh,xz,hz,zb,zy,by$$

form an $xy$-butterfly. Indeed, $b,y\notin\{x,h\}$ because $x\to z$ and $h\to z$, whereas $z\to b$ and $z\to y$. This is the argument of [10, Fact 18]; we include it to keep track of the order bound.

Since $n\geq 15\ell-60$ and $\ell\geq 7$, we have

$$4+(\ell-7)=\ell-3\leq D.$$

Lemma 2.5(i) gives a path $P$ of length $\ell-7$ from $y$ to a vertex $v$, otherwise avoiding $\{x,h,z,b\}$. Delete

$$\{h,z,b\}\cup(V(P)\setminus\{v\})$$

and call the remaining graph $H$. Exactly $r=\ell-4$ vertices are deleted.

Write $n=3m+s$ with $s\in\{0,1,2\}$. Then

$$|H|=3m+s-r,\qquad\delta^{0}(H)\geq m+1-r.$$

Moreover, $n\geq 15\ell-60$ gives $m\geq 5\ell-20=5r$ since $s\leq 2$, and hence

$$7(m+1-r)-\bigl(2(3m+s-r)+3\bigr)=m-5r+4-2s\geq 0.$$

Also $m+1-r\geq 4\ell-15\geq 3$. Lemma 2.2 therefore gives a $v$–$x$ path in $H$ of some length $t\in\{3,4,5\}$. Choose the $x$–$y$ path of length $7-t$ in the butterfly. Together with $P$ and the $v$–$x$ path, it forms a simple cycle of length

$$(7-t)+(\ell-7)+t=\ell.$$

∎

Together with Lemmas 16, 17 and 19 of Kelly, Kühn and Osthus [10], Corollary 2.7 replaces the order hypothesis in their Theorem 4 by $n\geq\ell$ for $\ell=4,5,6$, and by $n\geq 15\ell-60$ for $\ell\geq 7$.

Taking $\ell=3q$ in Corollary 2.7 gives the following bound when $3\nmid n$.

Corollary 2.8.

Let $q\geq 3$, let $3\nmid n$, and suppose $n\geq 45q-60$. If $G$ is an oriented graph on $n$ vertices with

$$\delta^{0}(G)\geq\left\lceil\frac{n}{3}\right\rceil,$$

then every vertex of $G$ lies on a copy of $C_{3q}$.

Proof.

Since $3\nmid n$,

$$\left\lceil\frac{n}{3}\right\rceil=\left\lfloor\frac{n}{3}\right\rfloor+1.$$

Apply Corollary 2.7 with $\ell=3q$. ∎

We next isolate the equality structure produced by an independent outneighbourhood.

Lemma 2.9.

Let $G$ be an oriented graph on $3m$ vertices with $\delta^{0}(G)\geq m$. If $N^{+}(z)$ is independent, then, with

$$A=N^{+}(z),\qquad B=V(G)\setminus A,$$

we have $|A|=m$, $|B|=2m$, and

$$d_{B}^{+}(a)=d_{B}^{-}(a)=m\qquad\text{for every }a\in A.$$

In particular, each pair in $A\times B$ is joined by exactly one arc.

Proof.

Lemma 2.1(ii) gives $|A|\leq m$, while $d^{+}(z)\geq m$ gives $|A|\geq m$. Thus $|A|=m$. Since $A$ is independent, every in- and outneighbour of $a\in A$ lies in $B$. The two neighbourhoods are disjoint, have size at least $m$ each, and lie in the $2m$-set $B$, so equality holds throughout. ∎

We call a partition $(A,B)$ of $V(G)$ a balanced cut if, for some integer $m$, the set $A$ is independent, $|A|=m$, $|B|=2m$, and

$$d_{B}^{+}(a)=d_{B}^{-}(a)=m\qquad\text{for every }a\in A.$$

If $A=N^{+}(z)$, we say that the balanced cut is rooted at $z$.

In a balanced cut, put

$$O(a):=N_{B}^{+}(a)\qquad(a\in A).$$

Thus every row $O(a)$ has size $m$. For $b\in B$, define

$$s_{b}:=|N_{A}^{-}(b)|=|\{a\in A:a\to b\}|,\qquad t_{b}:=m-s_{b}=|N_{A}^{+}(b)|.$$

The semidegree condition gives the fundamental inequalities

(5) $$d_{B}^{+}(b)\geq s_{b},\qquad d_{B}^{-}(b)\geq t_{b},\qquad\sum_{b\in B}s_{b}=\sum_{b\in B}t_{b}=m^{2}.$$

3. Nonextendable endpoints and row-family stability

Throughout the first part of this section, $(A,B)$ is a balanced cut and $x\in B$ satisfies $x\to A$. Thus $x\notin O(a)$ for every $a\in A$. A $D_{3}$-transition into $a$ is a simple path

$$a^{\prime}\to b\to c\to a,\qquad a^{\prime}\in A\setminus\{a\},\quad b,c\in B\setminus\{x\}.$$

Lemma 3.1.

If $m\geq 3$, then at most three vertices of $A$ admit no $D_{3}$-transition.

Proof.

Call such a vertex $a$ nonextendable and put

$$J_{a}=N_{B}^{-}(a)\setminus\{x\},\qquad|J_{a}|=m-1,$$

and

$$L_{a}=\{b\in B\setminus\{x\}:N_{A}^{-}(b)\subseteq\{a\}\}.$$

If $c\in J_{a}$, then every inneighbour of $c$ in $B\setminus\{x\}$ lies in $L_{a}$; otherwise some $b\to c$ has an inneighbour $a^{\prime}\in A\setminus\{a\}$, giving $a^{\prime}\to b\to c\to a$.

Nonextendable vertices with $L_{a}=\varnothing$. For $c\in J_{a}$, the only possible inneighbour of $c$ in $B$ is $x$, so $d_{B}^{-}(c)\leq 1$. By (5), $t_{c}\leq 1$, while $c\to a$ gives $t_{c}\geq 1$. Hence $t_{c}=1$ and $a$ is the unique outneighbour of $c$ in $A$. It follows that the sets $J_{a}$ belonging to distinct nonextendable vertices with $L_{a}=\varnothing$ are pairwise disjoint. Since three such sets have total size $3(m-1)>2m-1=|B\setminus\{x\}|$, there are at most two nonextendable vertices of this kind.

Nonextendable vertices with $L_{a}\neq\varnothing$. We show that there is at most one. Suppose that distinct nonextendable vertices $a,a^{\prime}$ have nonempty $L_{a},L_{a^{\prime}}$. First, these sets are disjoint. Indeed, if $L_{0}=L_{a}\cap L_{a^{\prime}}$ is nonempty, then every $z\in L_{0}$ has $s_{z}=0$ and $t_{z}=m$. Moreover, $z\in J_{a}\cap J_{a^{\prime}}$, and all its inneighbours in $B\setminus\{x\}$ lie in $L_{0}$. Therefore every $z\in L_{0}$ has at least $m-1$ inneighbours in $L_{0}$, and

$$|L_{0}|(m-1)\leq e(L_{0})\leq\binom{|L_{0}|}{2}.$$

Thus $|L_{0}|\geq 2m-1$. On the other hand, $t_{x}=m$ and $\sum_{b\in B}t_{b}=m^{2}$, so $(|L_{0}|+1)m\leq m^{2}$, giving $|L_{0}|\leq m-1$, a contradiction.

Write $k=|L_{a}|$ and $k^{\prime}=|L_{a^{\prime}}|$. For $z\in L_{a}$, we have $s_{z}\leq 1$ and hence $t_{z}\geq m-1$. Since $a^{\prime}\neq a$, the definition of $L_{a}$ gives $z\to a^{\prime}$, so $z\in J_{a^{\prime}}$. Nonextendability of $a^{\prime}$ implies that at least $m-2$ inneighbours of $z$ lie in $L_{a^{\prime}}$. Consequently,

$$e(L_{a^{\prime}},L_{a})\geq k(m-2).$$

Symmetrically, $e(L_{a},L_{a^{\prime}})\geq k^{\prime}(m-2)$. The two sets are disjoint and the graph is oriented, so at most one of the two possible arcs occurs on each pair in $L_{a}\times L_{a^{\prime}}$. Therefore

$$(k+k^{\prime})(m-2)\leq e(L_{a^{\prime}},L_{a})+e(L_{a},L_{a^{\prime}})\leq kk^{\prime}.$$

Furthermore,

$$m+(k+k^{\prime})(m-1)\leq\sum_{b\in B}t_{b}=m^{2},$$

so $k+k^{\prime}\leq m$. Consequently,

$$m-2\leq\frac{kk^{\prime}}{k+k^{\prime}}\leq\frac{k+k^{\prime}}{4}\leq\frac{m}{4},$$

which is impossible for $m\geq 3$. Hence at most one nonextendable vertex has nonempty $L_{a}$, and the total number of nonextendable vertices is at most three. ∎

We now turn to the set-system statement. Let $U$ be a finite set, let $C\subseteq U$, and let $\mathcal{O}=(O_{i}:i\in I)$ be a family of equal-sized subsets of $U$, each meeting $C$. A terminal-safe three-chain consists of four distinct indices $i_{0},i_{1},i_{2},i_{3}$ and four pairwise distinct elements $b_{0},b_{1},b_{2},d$ such that

$$b_{j}\in O_{i_{j}}\setminus O_{i_{j+1}}\quad(0\leq j\leq 2),\qquad d\in O_{i_{3}}\cap C.$$

Lemma 3.2.

Let $S_{1},S_{2},S_{3},S_{4}$ be four distinct $k$-subsets of a set $U$. There is a cyclic ordering of these sets and pairwise distinct elements

$$z_{i}\in S_{i}\setminus S_{i+1}\qquad(i\in\mathbb{Z}/4\mathbb{Z}).$$

Proof.

For a cyclic order $T_{1},T_{2},T_{3},T_{4}$, put

$$D_{i}=T_{i}\setminus T_{i+1}\qquad(i\in\mathbb{Z}/4\mathbb{Z}).$$

We have $D_{i}\cap D_{i+1}=\varnothing$: membership in $T_{i+1}$ is required by $D_{i+1}$ and forbidden by $D_{i}$. Consequently,

$$(D_{1}\cup D_{3})\cap(D_{2}\cup D_{4})=\varnothing.$$

Thus the four sets $D_{i}$ have a system of distinct representatives if and only if each opposite pair $(D_{1},D_{3})$ and $(D_{2},D_{4})$ has two distinct representatives; representatives chosen for different opposite pairs are automatically distinct. Each $D_{i}$ is nonempty, because consecutive sets have the same size and are distinct. Hence an opposite pair fails Hall’s condition precisely when its two members are the same singleton.

Write

$$\Delta(P,Q)=|P\setminus Q|=|Q\setminus P|$$

and call a pair $ij$ coarse if $\Delta(S_{i},S_{j})\geq 2$. If two coarse pairs are adjacent, extend them to a Hamilton cycle on the four labels. The two coarse directed differences belong to different opposite pairs, so neither opposite pair can be the same-singleton obstruction.

It remains to consider the case where the graph of coarse pairs is a matching. Suppose first that it is nonempty, and relabel so that $12$ is coarse. Then $13,14,23,24$ are thin, meaning that their $\Delta$-value is one. Consider the cycles

$$1234,\quad 1432,\quad 1243,\quad 1342.$$

In each order, the coarse edge $12$ supplies a difference set of size at least two to one opposite pair, so only the other opposite pair can obstruct a rainbow choice. If all four cycles fail, the four obstructions are as follows:

$$\begin{array}[]{c|c}\text{cyclic order}&\text{same-singleton obstruction}\\ \hline\cr 1234&S_{2}\setminus S_{3}=S_{4}\setminus S_{1}=\{a\}\\ 1432&S_{1}\setminus S_{4}=S_{3}\setminus S_{2}=\{b\}\\ 1243&S_{2}\setminus S_{4}=S_{3}\setminus S_{1}=\{c\}\\ 1342&S_{1}\setminus S_{3}=S_{4}\setminus S_{2}=\{d\}\end{array}$$

Here $a,c\in S_{2}$ and $b,d\notin S_{2}$. Also $a\neq c$ and $b\neq d$, since either equality would impose contradictory membership in $S_{4}$ or $S_{3}$, respectively. Thus $a,b,c,d$ are pairwise distinct, and

$$S_{3}=(S_{2}\setminus\{a\})\cup\{b\},\qquad S_{4}=(S_{2}\setminus\{c\})\cup\{d\},$$

and

$$S_{1}=(S_{2}\setminus\{a,c\})\cup\{b,d\}.$$

For the cycle $1324$, the four directed differences contain, in order, $d,b,c,a$, a contradiction.

Finally, suppose there is no coarse pair. Write

$$S_{1}=K\cup\{p\},\qquad S_{2}=K\cup\{q\}.$$

Every $k$-set $S\notin\{S_{1},S_{2}\}$ satisfying $\Delta(S,S_{1})=\Delta(S,S_{2})=1$ has exactly one of the forms

$$K\cup\{r\},\quad r\notin K\cup\{p,q\},\qquad\text{or}\qquad(K\setminus\{r\})\cup\{p,q\},\quad r\in K.$$

A set of the first form and one of the second form have $\Delta$-value two. Hence $S_{3},S_{4}$ have the same form, and all four sets are either $K\cup\{r_{i}\}$ or $L\setminus\{r_{i}\}$, where $L:=K\cup\{p,q\}$. In the first case any cyclic order has the distinct witnesses $r_{i}$; in the second it has the distinct witnesses $r_{i+1}$. ∎

Corollary 3.3.

If four distinct row types occur in $\mathcal{O}$, then $\mathcal{O}$ has a terminal-safe three-chain.

Proof.

Take a rainbow cycle $T_{0}T_{1}T_{2}T_{3}T_{0}$ with witnesses $z_{i}\in T_{i}\setminus T_{i+1}$. If some $z_{j}\in C$, delete the outgoing edge $T_{j}T_{j+1}$, order the remaining path as

$$T_{j+1},T_{j+2},T_{j+3},T_{j},$$

and use $z_{j}$ as the terminal representative. If no $z_{i}$ lies in $C$, delete any edge and choose an arbitrary element of the final row in $C$ as the terminal representative. In either case the four representatives are distinct. ∎

The preceding lemma yields the following classification.

Proposition 3.4.

Let $|I|\geq 4$, and let every row $O_{i}$ be a $k$-subset of $U$ meeting $C$. The family has no terminal-safe three-chain if and only if one of the following holds.

1. There is one row type.

2. There are exactly two row types $X,Y$, and either one has multiplicity one, or both have multiplicity at least two and $|X\setminus Y|=1$.

3. There are exactly three row types of one of the following forms:

   $$K\cup\{p\},\quad K\cup\{q\},\quad K\cup\{r\},$$

   or

   $$L\setminus\{p\},\quad L\setminus\{q\},\quad L\setminus\{r\},$$

   where $p,q,r$ are distinct, and the common intersection of the three rows is disjoint from $C$.

Proof.

Corollary 3.3 excludes four row types. If there is one row type, then every difference $O_{i_{j}}\setminus O_{i_{j+1}}$ is empty, so no terminal-safe three-chain exists.

Suppose there are two types $X,Y$. A four-index chain exists only if both types occur at least twice, and then the type sequence must alternate. Put $P=X\setminus Y$ and $Q=Y\setminus X$. If $|P|\geq 2$, choose two distinct representatives from the two copies of $P$, choose $d\in Y\cap C$, and choose a representative from $Q$ distinct from $d$; this is possible because $|Q|=|P|\geq 2$. Conversely, if $|P|=1$, the two $P$-positions cannot receive distinct representatives. This proves (ii).

Now suppose there are three types. Some type, say $X$, occurs at least twice; call the other types $Y,Z$. For the type sequence $Y,X,Z,X$, the four representative sets are

$$Y\setminus X,\quad X\setminus Z,\quad Z\setminus X,\quad X\cap C.$$

All four sets are nonempty: the first three because the row types are distinct and equicardinal, and the last because every row meets $C$. The first and third lie outside $X$, whereas the second and fourth lie inside $X$. Thus the union of the outside pair is disjoint from the union of the inside pair. As in Lemma 3.2, an SDR exists if and only if each pair has two distinct representatives, and a pair fails precisely when its two members are the same singleton. Hence Hall’s condition fails exactly when

(6) $$Y\setminus X=Z\setminus X=\{p\},$$

or

(7) $$X\setminus Z=X\cap C=\{q\}.$$

For the sequence $Z,X,Y,X$, failure is equivalent to (6) or

(8) $$X\setminus Y=X\cap C=\{q\}.$$

Thus either (6) holds, or both (7) and (8) hold.

In the first case, equal row sizes give

$$X=L\setminus\{p\},\qquad Y=L\setminus\{y\},\qquad Z=L\setminus\{z\}$$

for distinct $p,y,z$. In the second case,

$$X=K\cup\{q\},\qquad Y=K\cup\{p\},\qquad Z=K\cup\{r\}$$

for distinct $p,q,r$. Thus the types have one of the two forms in part (iii).

In the first form, if the common intersection contained $d\in C$, then the sequence $X,Y,X,Z$ would have the three distinct hub representatives together with $d$, giving a terminal-safe three-chain. In the second form, $X\cap C=\{q\}$ already implies $K\cap C=\varnothing$. Conversely, for either family with $C$-free common intersection, every difference representative and every terminal representative lies in the same three-point hub. Four distinct representatives are impossible. ∎

Corollary 3.5.

If a row family indexed by $I$, $|I|\geq 4$, has no terminal-safe three-chain, then either

1. one row type has multiplicity at least $|I|-1$, or

2. $$\left|\left(\bigcup_{i\in I}O_{i}\right)\setminus\left(\bigcap_{i\in I}O_{i}\right)\right|\leq 3.$$

Proof.

In Proposition 3.4(ii), a singleton type leaves the other type with multiplicity $|I|-1$; otherwise the two types have total variation two. In case (iii), the total variation is exactly the three-point hub. ∎

4. The root-dominating balanced cut

In this section, $G$ has order $3m$ and minimum semidegree at least $m$, $(A,B)$ is a balanced cut, and $x\in B$ satisfies $x\to A$. Put

$$C=N_{B}^{-}(x),\qquad U=B\setminus\{x\}.$$

Every row $O(a)$ is an $m$-subset of the $(2m-1)$-set $U$, while $|C|\geq m$. Hence

(9) $$O(a)\cap C\neq\varnothing\qquad\text{for every }a\in A.$$

We first handle $C_{6}$ directly.

Proposition 4.1.

If $m\geq 9$, then $x$ lies on a copy of $C_{6}$.

Proof.

Let $W$ be the set of nonextendable endpoints from Lemma 3.1, so $|W|\leq 3$. Suppose first that some $a\in A\setminus W$ satisfies $|O(a)\cap C|\geq 2$. Choose a $D_{3}$-transition

$$a_{0}\to b\to c\to a.$$

Since $c\to a$, we have $c\notin O(a)$. Choose

$$d\in(O(a)\cap C)\setminus\{b\}.$$

Then

$$x\to a_{0}\to b\to c\to a\to d\to x$$

is a $C_{6}$.

We may therefore assume that $|O(a)\cap C|=1$ for every $a\in A\setminus W$. Since there is at least one such row, the inequality

$$|O(a)\cap C|\geq|O(a)|+|C|-|U|=|C|-m+1$$

implies $|C|\leq m$. On the other hand, $x\to A$, so $x$ has no inneighbour in $A$ and

$$|C|=d_{B}^{-}(x)=d^{-}(x)\geq m.$$

Thus $|C|=m$. Put $D=U\setminus C$, so $|D|=m-1$. Every extendable row has the form

$$O(a)=D\cup\{d_{a}\},\qquad d_{a}\in C.$$

Thus $s_{b}\geq m-3$ for every $b\in D$, and (5) gives

$$e(D,C) \geq(m-1)(m-3)-\binom{m-1}{2}-(m-1)$$

(10) $$=\frac{(m-1)(m-6)}{2}.$$

For $m\geq 9$,

$$\frac{(m-1)(m-6)}{2}-(m-1)=\frac{(m-1)(m-8)}{2}>0.$$

We claim that there are $b\in D$, $c\in C$, and $a\in A\setminus W$ such that $b\to c$ and $d_{a}\neq c$. Otherwise, for every arc $b\to c$ from $D$ to $C$ and every extendable row label $d_{a}$, we would have $d_{a}=c$. The lower bound (10) is positive, and $A\setminus W$ is nonempty, so all targets of arcs from $D$ to $C$ and all extendable row labels would equal a single vertex $c_{*}$. This would give

$$e(D,C)=e(D,\{c_{*}\})\leq|D|=m-1,$$

a contradiction. Since $|A\setminus W|\geq m-3\geq 2$, choose another extendable vertex $a_{0}\neq a$. Then

$$x\to a_{0}\to b\to c\to a\to d_{a}\to x$$

is a $C_{6}$. ∎

We now close all longer multiples of three under the linear order hypothesis of Theorem 1.1.

Proposition 4.2.

Let $q\geq 3$, put $\ell=3q$, and suppose $n=3m\geq n_{0}(q)$. Then $x$ lies on a copy of $C_{\ell}$.

Proof.

Since $n=3m\geq n_{0}(q)$,

$$m\geq\begin{cases}33,&q=3,\\ 15q-2,&q\geq 4.\end{cases}$$

In particular,

(11) $$m\geq\ell,\qquad m\geq 2q+11,\qquad m-4\geq q.$$

Let $W$ be the nonextendable-endpoint set and put $A_{0}=A\setminus W$. Thus $|W|\leq 3$ and every $a\in A_{0}$ admits a $D_{3}$-transition. Apply Corollary 3.5 to the rows indexed by $A_{0}$, with terminal set $C$.

The proof follows the three outcomes in Corollary 3.5. A terminal-safe three-chain gives three possible initial lengths and is closed by short linking. In each of the two remaining outcomes, (5) gives a dense bipartite graph, and König’s theorem supplies the required matching.

Case 1: a terminal-safe three-chain. Suppose first that there is a terminal-safe three-chain. It yields distinct vertices with

(12) $$x\to a_{0}\to b_{0}\to a_{1}\to b_{1}\to a_{2}\to b_{2}\to a_{3}\to d\to x.$$

If $q=3$, this is already a $C_{9}$. Assume $q\geq 4$. The suffixes of (12) give $x$–$a_{3}$ paths

$$Q_{3}=xa_{2}b_{2}a_{3},\qquad Q_{5}=xa_{1}b_{1}a_{2}b_{2}a_{3}$$

of lengths three and five. Since $a_{3}\notin W$, take a transition

$$a^{\prime}\to u\to v\to a_{3}.$$

Then

$$Q_{4}=xa^{\prime}uva_{3}$$

is a simple path of length four. Different candidate paths may intersect; only one will eventually be used. Let $Z$ be the union of their internal vertices. Then $|Z|\leq 7$.

Since $|Z|\leq 7$, we have

$$|Z|+1+\ell-8\leq\ell\leq m,\qquad 15(|Z|+\ell-8)+7\leq 15(\ell-1)+7=n_{0}(q).$$

Lemma 2.5(iii), with $B=8$, now closes one of $Q_{3},Q_{4},Q_{5}$ to a $C_{\ell}$.

Case 2: a dominant row. Suppose that a row type $S$ occurs at least

$$|A_{0}|-1\geq m-4$$

times. For every $b\in S$, we have $s_{b}\geq m-4$, so

(13) $$e(S,B\setminus S)\geq m(m-4)-\binom{m}{2}=\frac{m^{2}-7m}{2}.$$

Choose $d\in S\cap C$, which exists by (9), and form the bipartite graph with parts

$$S\setminus\{d\}\quad\text{and}\quad(B\setminus S)\setminus\{x\},$$

joining $b$ to $c$ precisely when $b\to c$ in $G$. Deleting the source $d$ and the target $x$ removes at most $2m$ arcs from (13), so this bipartite graph has at least $(m^{2}-11m)/2$ edges. If its maximum matching had size at most $q-2$, König’s theorem would give a vertex cover of size at most $q-2$. Every vertex of the bipartite graph has degree at most $m$, so the cover would meet at most $(q-2)m$ edges. By (11),

$$\frac{m^{2}-11m}{2}-(q-2)m=\frac{m}{2}(m-2q-7)>0,$$

a contradiction. Take a matching

$$b_{i}\to c_{i}\qquad(0\leq i\leq q-2)$$

and distinct $S$-type vertices $a_{0},\ldots,a_{q-1}$. These choices are available because $m-4\geq q$ by (11). Then

$$x\to a_{0}\to b_{0}\to c_{0}\to a_{1}\to\cdots\to b_{q-2}\to c_{q-2}\to a_{q-1}\to d\to x$$

is a $C_{3q}$.

Case 3: variation on at most three points. Suppose the active variation has size at most three. Put

$$K=\bigcap_{a\in A_{0}}O(a),\qquad V=\left(\bigcup_{a\in A_{0}}O(a)\right)\setminus K,\qquad L=B\setminus(K\cup V).$$

Write $v=|V|$ and $|K|=m-r$. Every row is $K\cup P_{a}$ with $P_{a}\subseteq V$ and $|P_{a}|=r$. If $v>0$, each point of $V$ appears in some but not all rows, so $1\leq r\leq v-1$. Hence

$$(v,r)\in\{(0,0),(2,1),(3,1),(3,2)\}.$$

Every $b\in K$ belongs to all rows indexed by $A_{0}$, and therefore $s_{b}\geq m-3$. Since $|L|=m+r-v\leq m$, we obtain

$$e(K,L) \geq|K|(m-3)-\binom{|K|}{2}-|K|v$$

$$=\frac{(m-r)(m+r-5-2v)}{2}$$

(14) $$\geq\frac{m^{2}-11m+10}{2}.$$

Fix $a_{*}\in A_{0}$ and $d\in O(a_{*})\cap C$. Since $x$ belongs to no row, $x\in L$. Form the bipartite graph whose left part is $K\setminus\{d\}$ if $d\in K$ and is $K$ otherwise, whose right part is $L\setminus\{x\}$, and whose edges are the arcs directed from left to right. Deleting the target $x$ and, when necessary, the source $d$ removes at most $2m$ arcs from (14); hence at least $(m^{2}-15m+10)/2$ edges remain. If there were no matching of size $q-1$, König’s theorem would give a vertex cover of size at most $q-2$. Both parts have size at most $m$, so such a cover would meet at most $(q-2)m$ edges. By (11),

$$m^{2}-(2q+11)m+10>0$$

and hence there is a matching $b_{i}\to c_{i}$ of size $q-1$ from $K$ to $L$, avoiding $d$ and $x$. Since $|A_{0}|\geq m-3\geq q$, choose distinct $a_{0},\ldots,a_{q-1}\in A_{0}$ with $a_{q-1}=a_{*}$. Since every row contains $K$ and avoids $L$,

$$x\to a_{0}\to b_{0}\to c_{0}\to a_{1}\to\cdots\to b_{q-2}\to c_{q-2}\to a_{q-1}\to d\to x$$

is again a $C_{3q}$. ∎

5. The transitive-entry balanced cut

We now consider a balanced cut $(A,B)$ rooted at $z$, together with distinct vertices $x,h,z\in B$ satisfying

(15) $$z\to A,\qquad x\to h\to z,\qquad x\to z.$$

The prescribed vertex is $x$, not $z$.

Proposition 5.1.

Let $q\geq 2$, put $\ell=3q$, and suppose $n=3m\geq n_{0}(q)$. Under (15), the vertex $x$ lies on a copy of $C_{\ell}$.

Proof.

Since $n=3m\geq n_{0}(q)$, we have

$$m\geq\begin{cases}13,&if~q=2,\\ 33,&if~q=3,\\ 15q-2,&if~q\geq 4.\end{cases}$$

In particular,

(16) $$m\geq\ell,\qquad m\geq 2q-1,\qquad m\geq q.$$

We distinguish whether $x$ sends an arc to $A$, whether the rows are distinct, and whether all rows are equal. The first two cases use three initial path lengths and short linking. The last case uses a bipartite matching.

Case 1: an arc from $x$ to $A$. Suppose first that $x\to a$ for some $a\in A$. There are $x$–$a$ paths of lengths one, two, and three:

$$xa,\qquad xza,\qquad xhza.$$

With $B=6$ and $Z=\{h,z\}$, put $R=|Z|+\ell-B=\ell-4$. The two numerical conditions in Lemma 2.5(iii) are

$$\ell-3\leq m\qquad\text{and}\qquad 15R+7=45q-53\leq n_{0}(q).$$

Thus that lemma gives a $C_{\ell}$ through $x$. This includes the case $\ell=B=6$.

Case 2: two distinct rows. We may assume that $A\to x$ and that two rows $O(a),O(a^{\prime})$ are distinct. Since $x$ belongs to every row and $z$ belongs to none, choose

$$b\in O(a)\setminus O(a^{\prime})$$

with $b\notin\{x,z\}$. Then $a\to b\to a^{\prime}$. If $\ell\geq 9$, the three $x$–$a^{\prime}$ paths

$$xza^{\prime},\qquad xhza^{\prime},\qquad xzaba^{\prime}$$

have lengths two, three, and four. Apply Lemma 2.5(iii) with $B=7$ and $Z=\{h,z,a,b\}$. Indeed,

$$|Z|\leq 4,\qquad|Z|+1+\ell-B\leq\ell-2\leq m,\qquad R=|Z|+\ell-B\leq\ell-3,$$

and, since $q\geq 3$,

$$15R+7\leq 45q-38\leq n_{0}(q).$$

If $\ell=6$, choose the order of the two rows so that $b\neq h$. This is always possible: if $O(a)\setminus O(a^{\prime})=\{h\}$, then every element of $O(a^{\prime})\setminus O(a)$ differs from $h$. Now

$$x\to h\to z\to a\to b\to a^{\prime}\to x$$

is a $C_{6}$.

Case 3: all rows are equal. It remains that $A\to x$ and all rows are equal to one $m$-set $S$. Then $x\in S$ and $z\notin S$. Every $b\in S$ has $s_{b}=m$, and hence

$$e(S,B\setminus S)\geq m^{2}-\binom{m}{2}=\frac{m(m+1)}{2}.$$

Form the bipartite graph with source part $S\setminus\{x\}$, target part $(B\setminus S)\setminus\{z\}$, and an edge $bc$ whenever $b\to c$. Deleting the source $x$ removes at most $m$ arcs. After that deletion, the target $z$ is incident with at most $m-1$ remaining sources. Equivalently, the known arc $x\to z$ is not counted twice in the two deletions. Hence at least

$$\frac{(m-1)(m-2)}{2}$$

edges remain. If there were no matching of size $q-1$, König’s theorem would give a vertex cover of size at most $q-2$, which meets at most $(q-2)(m-1)$ edges. By (16),

$$\frac{(m-1)(m-2)}{2}-(q-2)(m-1)=\frac{m-1}{2}(m-2q+2)>0,$$

a contradiction. A matching $b_{i}\to c_{i}$ of size $q-1$ and distinct vertices $a_{0},\ldots,a_{q-1}\in A$, available because $m\geq q$ by (16), yield

$$x\to z\to a_{0}\to b_{0}\to c_{0}\to a_{1}\to\cdots\to b_{q-2}\to c_{q-2}\to a_{q-1}\to x,$$

a cycle of length $3q$. ∎

6. The butterfly branch and the main theorem

The next lemma adapts [10, Lemma 19]. Its point is that, when $3\mid n$, the butterfly argument lowers the semidegree hypothesis from $n/3+1$ to $n/3$.

Lemma 6.1.

Let $G$ be an oriented graph on $n$ vertices, put $d=\lceil n/3\rceil$, and suppose $d\geq 3$ and $\delta^{0}(G)\geq d$. If $G$ contains an $xy$-butterfly, then $x$ lies on a copy of $C_{6}$.

Proof.

Write the butterfly vertices as $x,h,z,b,y$, with arcs

$$xh,xz,hz,zb,zy,by.$$

We first translate the absence of a $C_{6}$ through $x$ into three restrictions on return paths from $y$ to $x$. Two neighbourhood layers then have only one possible overlap, and a cardinality estimate forces that overlap to contain a vertex different from $z$.

The butterfly contains the $x$–$y$ paths

$$xhzby,\qquad xhzy,\qquad xzy$$

of lengths four, three, and two, respectively. Any $y$–$x$ path of length two automatically avoids $h,z,b$: using one of these vertices as its internal vertex would contradict, respectively, $x\to h$, $z\to y$, or $b\to y$. Such a path therefore closes with $xhzby$. A length-three $y$–$x$ path cannot contain $z$, because $z\to y$ and $x\to z$; if it also avoids $h$, it closes with $xhzy$. Finally, a length-four $y$–$x$ path avoiding $z$ closes with $xzy$. Thus, if no $C_{6}$ through $x$ exists, we may assume that

1. there is no $y$–$x$ path of length two;

2. there is no $y$–$x$ path of length three avoiding $h$;

3. there is no $y$–$x$ path of length four avoiding $z$.

Choose

$$Y\subseteq N^{+}(y)\setminus\{h,x\},\quad|Y|=d-2,\qquad X\subseteq N^{-}(x)\setminus\{y\},\quad|X|=d-1.$$

Set

$$Y^{\prime}=N^{+}(Y)\setminus Y,\qquad X^{\prime}=N^{-}(X)\setminus X.$$

The three assumptions imply

$$X\cap Y=X\cap Y^{\prime}=Y\cap X^{\prime}=\varnothing.$$

Indeed, a vertex in $X\cap Y$ gives a length-two $y$–$x$ path. If $w\in X\cap Y^{\prime}$, choose $u\in Y$ with $u\to w$; then $y\to u\to w\to x$. If $w\in Y\cap X^{\prime}$, choose $v\in X$ with $w\to v$; then $y\to w\to v\to x$. In both length-three paths the internal vertices avoid $h$, since $h\notin X$ by $x\to h$ and $h\notin Y$ by the definition of $Y$. They also imply that $x,y$ lie in none of $X,Y,X^{\prime},Y^{\prime}$. Indeed, the definitions exclude $x$ from $X,Y$ and $y$ from $X,Y$; if $x\in Y^{\prime}$ or $y\in X^{\prime}$, then there is a $y$–$x$ path of length two, while orientedness excludes $x\in X^{\prime}$ and $y\in Y^{\prime}$. By Lemma 2.1,

$$|Y^{\prime}|\geq\left\lceil\frac{d+3}{2}\right\rceil,\qquad|X^{\prime}|\geq\left\lceil\frac{d+2}{2}\right\rceil,$$

and hence $|X^{\prime}|+|Y^{\prime}|\geq d+3$. Since every overlap among the four sets is contained in $X^{\prime}\cap Y^{\prime}$, we obtain

$$n+|X^{\prime}\cap Y^{\prime}|\geq|X|+|Y|+|X^{\prime}|+|Y^{\prime}|+2\geq 3d+2.$$

Since $n\leq 3d$, we have $|X^{\prime}\cap Y^{\prime}|\geq 2$. Choose $w\in(X^{\prime}\cap Y^{\prime})\setminus\{z\}$. There are vertices $u\in Y$ and $v\in X$ such that

$$y\to u\to w\to v\to x.$$

Since $z\notin Y$ by $z\to y$, $z\notin X$ by $x\to z$, and $w\neq z$, this is a length-four path avoiding $z$, contradicting (iii). ∎

For $q\geq 3$, the three paths in a butterfly can be combined with the short-linking lemma.

Lemma 6.2.

Let $q\geq 3$, put $\ell=3q$, and let $G$ be an oriented graph on $n\geq n_{0}(q)$ vertices with $\delta^{0}(G)\geq\lceil n/3\rceil$. If $G$ contains an $xy$-butterfly, then $x$ lies on a copy of $C_{\ell}$.

Proof.

Let $x,h,z,b,y$ be the butterfly vertices, and put $B=7$ and $Z=\{h,z,b\}$. The butterfly supplies $x$–$y$ paths of lengths two, three, and four. Moreover,

$$|Z|+1+\ell-B=\ell-3\leq\left\lceil\frac{n}{3}\right\rceil,\qquad R=|Z|+\ell-B=\ell-4,$$

and, since $q\geq 3$,

$$15R+7=45q-53\leq n_{0}(q).$$

Lemma 2.5(iii) gives a $C_{\ell}$ through $x$. ∎

We can now prove the critical case.

Theorem 6.3.

Let $q\geq 2$, put $\ell=3q$, and let $G$ be an oriented graph on $n=3m\geq n_{0}(q)$ vertices with $\delta^{0}(G)\geq m$. Then every vertex of $G$ lies on a copy of $C_{\ell}$.

Proof.

Fix $x\in V(G)$. If $N^{+}(x)$ is independent, Lemma 2.9 gives the root-dominating balanced cut. Proposition 4.1 applies when $q=2$, and Proposition 4.2 applies when $q\geq 3$.

Suppose $N^{+}(x)$ is not independent. Choose an arc $h\to z$ inside $N^{+}(x)$. Thus

$$x\to h\to z,\qquad x\to z.$$

If $N^{+}(z)$ is independent, Lemma 2.9 gives the transitive-entry balanced cut, and Proposition 5.1 applies.

Finally, suppose $N^{+}(z)$ is not independent. Choose an arc $b\to y$ inside $N^{+}(z)$. The five vertices $x,h,z,b,y$ are distinct, and

$$xh,xz,hz,zb,zy,by$$

form an $xy$-butterfly. Apply Lemma 6.1 for $q=2$ and Lemma 6.2 for $q\geq 3$. ∎

Proof of Theorem 1.1.

Put $\ell=3q$ and fix $x\in V(G)$. If $3\mid n$, the result is Theorem 6.3. Suppose that $3\nmid n$ and put $d=\lceil n/3\rceil$. Lemma 2.1(ii) gives

$$|I|\leq n-2d<d$$

for every independent set $I$. Since every outneighbourhood has size at least $d$, none is independent. Choose an arc $h\to z$ inside $N^{+}(x)$, and then choose an arc $b\to y$ inside $N^{+}(z)$. The five vertices are distinct: $b,y$ cannot equal $x$ or $h$ because $x\to z$ and $h\to z$. Thus

$$xh,xz,hz,zb,zy,by$$

form an $xy$-butterfly. Lemma 6.1 applies when $q=2$, and Lemma 6.2 applies when $q\geq 3$. ∎

The following construction of Kelly, Kühn and Osthus [10, discussion following Theorem 4], with relabelled parts, proves that the semidegree bound in Corollary 1.2 is best possible. On $n-1$ vertices, take three independent sets $V_{1},V_{2},V_{3}$ whose sizes differ by at most one, and add all arcs

$$V_{1}\to V_{2},\qquad V_{2}\to V_{3},\qquad V_{3}\to V_{1}.$$

Add a vertex $u$ with

$$V_{1}\to u\to V_{2}$$

and no arcs between $u$ and $V_{3}$. The resulting oriented graph satisfies the following degree table, where $a=|V_{1}|$, $b=|V_{2}|$, and $c=|V_{3}|$:

$$\begin{array}[]{c|cc}\text{vertex class}&d^{+}&d^{-}\\ \hline\cr V_{1}&b+1&c\\ V_{2}&c&a+1\\ V_{3}&a&b\\ \{u\}&b&a\end{array}$$

Since $a,b,c$ differ by at most one, this gives

$$\delta^{0}(G)=\min\{a,b,c\}=\left\lfloor\frac{n-1}{3}\right\rfloor=\left\lceil\frac{n}{3}\right\rceil-1.$$

Every directed cycle through $u$ consists of the arc from $u$ to $V_{2}$, a path from $V_{2}$ to $V_{1}$ in the cyclic three-part core, and an arc from $V_{1}$ to $u$. The middle path has length $2$ modulo $3$, so the whole cycle has length $1$ modulo $3$. Hence $u$ lies on no $C_{3q}$, proving Corollary 1.2.

Remark 6.4.

Proposition 2.4 shows that the constant $+3$ in the linking inequality cannot be reduced and that the coefficient $21$ in Corollary 2.3 is asymptotically best possible. This does not determine the optimal coefficients in the order hypotheses of Theorem 1.1 or Corollary 2.7.

For $q\geq 4$, an argument that uses the remaining graph only through its order and minimum semidegree cannot lower $45q-8$ to $45q-9$. Indeed, put $\ell=3q$. If $n=45q-9=15\ell-9$ and the terminal-safe-chain branch deletes $r=\ell-1$ vertices, the remaining parameters are

$$N:=n-r=14\ell-8,\qquad d:=\frac{n}{3}-r=4\ell-2,$$

with

$$\delta^{0}(H)\geq d,\qquad 7d=2N+2.$$

With $c_{0}=2\ell-1$, the pair $(N,d)$ is the boundary pair in Proposition 2.4. Hence a smaller cutoff requires additional information about the remaining graph, such as the structure of the deleted path or the relation between the in- and outdegree losses. It remains open to determine the smallest constant $\gamma$ for which an order hypothesis of the form $n\geq\gamma q+O(1)$ suffices in Theorem 1.1.