Introduction
One of the best known and most studied open problems concerning oriented graphs is the following conjecture from 1978.
Conjecture 1.1 (Caccetta, Häggkvist [2 ] ). Every oriented graph G G G on n n n vertices with minimum outdegree δ + ( G ) ≥ n ℓ \delta^{+}(G) \ge\frac{n}{\ell} δ + ( G ) ≥ ℓ n contains a directed cycle of length at most ℓ \ell ℓ .
Here, by an oriented graph we understand a directed graph without loops and symmetric pairs of directed arcs, that is, an orientation of a simple graph. Furthermore, δ + ( G ) \delta^{+}(G) δ + ( G ) and δ − ( G ) \delta^{-}(G) δ − ( G ) denote the minimum outdegree and the minimum indegree of an oriented graph G G G , respectively.
Numerous partial results towards Conjecture 1.1 are known. These include proofs with an additive error term in the bound on the cycle length, proofs in which the minimum outdegree assumption is strengthened by a multiplicative constant, and results obtained under additional forbidden-subgraph assumptions. For these and related developments concerning the Caccetta–Häggkvist conjecture, we refer the reader to the survey [8 ] .
Even if we strengthen the assumption of Conjecture 1.1 by imposing a lower bound on the minimum semidegree δ ± ( G ) = min ( δ + ( G ) , δ − ( G ) ) \delta^{\pm}(G) = \min(\delta^{+}(G), \delta^{-}(G)) δ ± ( G ) = min ( δ + ( G ) , δ − ( G )) instead of the minimum outdegree, the essential difficulty seems to persist and the resulting weaker statement is open as well, except the case ℓ = 3 \ell= 3 ℓ = 3 recently claimed to be solved by OpenAI [7 ] . Motivated by this conjecture, Kelly, Kühn and Osthus [5 ] proposed in 2010 the following problem: for a given integer ℓ ≥ 4 \ell\ge4 ℓ ≥ 4 , determine the minimum semidegree that forces an oriented graph to contain a directed cycle of length exactly ℓ \ell ℓ . Despite the similar formulation, this problem is substantially different, and the answer depends on the divisibility properties of ℓ \ell ℓ . Indeed, Kelly, Kühn and Osthus conjectured the following.
Conjecture 1.2 (Kelly, Kühn, Osthus [5 ] ). Let ℓ ≥ 4 \ell\ge4 ℓ ≥ 4 be an integer and let k k k be the smallest integer greater than 2 that does not divide ℓ \ell ℓ . Then there exists n 0 n_0 n 0 such that every oriented graph G G G on n ≥ n 0 n \ge n_0 n ≥ n 0 vertices with minimum semidegree δ ± ( G ) ≥ ⌊ n k ⌋ + 1 \delta^{\pm}(G) \ge\left\lfloor\frac{n}{k} \right\rfloor+ 1 δ ± ( G ) ≥ ⌊ k n ⌋ + 1 contains a directed cycle of length ℓ \ell ℓ .
Kelly, Kühn and Osthus [5 ] proved Conjecture 1.2 in the case k = 3 k=3 k = 3 , that is, for cycle lengths not divisible by 3. They also showed an asymptotic statement (with the semidegree bound ( 1 + ε ) n k (1+\varepsilon)\frac{n}{k} ( 1 + ε ) k n ) in the cases k = 4 k=4 k = 4 and k = 5 k=5 k = 5 . Later, Kühn, Osthus and Piguet [6 ] proved a similar asymptotic statement for the remaining values of k k k , under the additional assumption that ℓ > 10 7 k 6 \ell> 10^7 k^6 ℓ > 1 0 7 k 6 . Conjecture 1.2 was then resolved in 2023, up to a slight adjustment of the semidegree bound.
Theorem 1.3 (Grzesik, Volec [4 ] ). Let ℓ ≥ 4 \ell\ge4 ℓ ≥ 4 be an integer and let k k k be the smallest integer greater than 2 that does not divide ℓ \ell ℓ . Then there exists n 0 n_0 n 0 such that for every oriented graph G G G on n ≥ n 0 n \ge n_0 n ≥ n 0 vertices:
if ℓ ≢ 3 ( m o d 12 ) \ell\not\equiv3 \pmod{12} ℓ ≡ 3 ( mod 12 ) and δ ± ( G ) ≥ n k + k − 1 2 k \delta^{\pm}(G) \ge\frac{n}{k}+\frac{k-1}{2k} δ ± ( G ) ≥ k n + 2 k k − 1 , then G G G contains a directed cycle of length ℓ \ell ℓ ,
if ℓ ≡ 3 ( m o d 12 ) \ell\equiv3 \pmod{12} ℓ ≡ 3 ( mod 12 ) and δ ± ( G ) ≥ n 4 + 1 4 \delta^{\pm}(G) \ge\frac{n}{4}+\frac{1}{4} δ ± ( G ) ≥ 4 n + 4 1 , then G G G contains a directed cycle of length ℓ \ell ℓ .
Moreover, the above bounds are best possible.
As with the Caccetta–Häggkvist conjecture, Conjecture 1.2 seems to hold in a stronger form, where the minimum semidegree is replaced by the minimum outdegree. However, the techniques used in the aforementioned results cannot be easily adapted to this stronger setting, as they heavily rely on bounding the directed diameter, which cannot be done without an assumption on the indegrees.
As a first step towards the outdegree version of Conjecture 1.2, Czygrinow, Molla, Nagle and Oursler [3 ] proved that for every integer ℓ ≥ 4 \ell\ge4 ℓ ≥ 4 , there exists n 0 n_0 n 0 such that every oriented graph G G G on n ≥ n 0 n \ge n_0 n ≥ n 0 vertices with minimum outdegree δ + ( G ) ≥ n 3 + 1 3 \delta^+(G) \ge\frac{n}{3}+\frac{1}{3} δ + ( G ) ≥ 3 n + 3 1 contains a directed cycle of length ℓ \ell ℓ . In particular, the outdegree version of Conjecture 1.2 holds whenever ℓ \ell ℓ is not divisible by 3.
In this paper, we improve the above result for large ℓ \ell ℓ divisible by 3, providing an optimal outdegree bound. In particular, this shows that the outdegree version of Conjecture 1.2 holds for every sufficiently large ℓ \ell ℓ , up to the same kind of slight adjustment of the degree bound as in Theorem 1.3.
Theorem 1.4. Let ℓ \ell ℓ be an integer divisible by 3 and let k k k be the smallest integer greater than 2 that does not divide ℓ \ell ℓ . If ℓ > 20 k 2 \ell> 20k^2 ℓ > 20 k 2 , then there exists n 0 n_0 n 0 such that every oriented graph G G G on n ≥ n 0 n \ge n_0 n ≥ n 0 vertices with δ + ( G ) ≥ n k + k − 1 k \delta^+(G) \ge\frac{n}{k}+\frac{k-1}{k} δ + ( G ) ≥ k n + k k − 1 contains a directed cycle of length ℓ \ell ℓ . Moreover, this outdegree bound is best possible if ℓ ≢ 3 , 6 ( m o d 12 ) \ell\not\equiv3,6 \pmod{12} ℓ ≡ 3 , 6 ( mod 12 ) and ℓ ≢ 24 , 48 ( m o d 60 ) \ell\not\equiv24,48 \pmod{60} ℓ ≡ 24 , 48 ( mod 60 ) .
Note that k k k is always a prime power, and so k > 9 k>9 k > 9 forces k ≥ 11 k\ge11 k ≥ 11 . In particular, when k > 9 k>9 k > 9 , the assumption ℓ > 20 k 2 \ell>20k^2 ℓ > 20 k 2 of Theorem 1.4 is redundant, as every such ℓ \ell ℓ satisfies it: all of the integers 3 , 4 , … , k − 1 3,4,\ldots,k-1 3 , 4 , … , k − 1 divide ℓ \ell ℓ , and hence ℓ ≥ lcm ( 3 , 4 , … , k − 1 ) > 20 k 2 \ell\ge\operatorname{lcm}(3,4,\ldots,k-1)>20k^2 ℓ ≥ lcm ( 3 , 4 , … , k − 1 ) > 20 k 2 . Thus, the assumption ℓ > 20 k 2 \ell>20k^2 ℓ > 20 k 2 can be replaced by ℓ > 1620 \ell>1620 ℓ > 1620 . A more careful analysis of our proof would reduce this bound even further, to ℓ > 180 \ell>180 ℓ > 180 , if needed.
Observe that the outdegree bound in Theorem 1.4 is slightly larger than the semidegree bound in Theorem 1.3 . At an intuitive level, this is because a larger family of extremal constructions is available when only the outdegree condition has to be maintained.
However, similarly as with ℓ ≡ 3 ( m o d 12 ) \ell\equiv3 \pmod{12} ℓ ≡ 3 ( mod 12 ) in Theorem 1.3 , there are cases in which the best known construction does not match the general bound in Theorem 1.4 . It turns out that in these cases the outdegree bound can indeed be improved, and the following theorem determines its optimal value.
Theorem 1.5. Let ℓ \ell ℓ be an integer divisible by 3 3 3 and let k k k be the smallest integer greater than 2 2 2 that does not divide ℓ \ell ℓ . Assume that ℓ > 20 k 2 \ell> 20k^2 ℓ > 20 k 2 , G G G is an oriented graph on n n n vertices, with n n n large enough, and one of the following assumptions is satisfied:
ℓ ≡ 3 ( m o d 12 ) \ell\equiv3 \pmod{12} ℓ ≡ 3 ( mod 12 ) and δ + ( G ) ≥ n 4 + 1 4 \delta^{+}(G) \ge\frac{n}{4} + \frac{1}{4} δ + ( G ) ≥ 4 n + 4 1 ;
ℓ ≡ 6 ( m o d 12 ) \ell\equiv6 \pmod{12} ℓ ≡ 6 ( mod 12 ) and δ + ( G ) ≥ n 4 + 2 4 \delta^{+}(G) \ge\frac{n}{4} + \frac{2}{4} δ + ( G ) ≥ 4 n + 4 2 ;
ℓ ≡ 24 ( m o d 60 ) \ell\equiv24 \pmod{60} ℓ ≡ 24 ( mod 60 ) and δ + ( G ) ≥ n 5 + 3 5 \delta^{+}(G) \ge\frac{n}{5} + \frac{3}{5} δ + ( G ) ≥ 5 n + 5 3 ;
ℓ ≡ 48 ( m o d 60 ) \ell\equiv48 \pmod{60} ℓ ≡ 48 ( mod 60 ) and δ + ( G ) ≥ n 5 + 2 5 \delta^{+}(G) \ge\frac{n}{5} + \frac{2}{5} δ + ( G ) ≥ 5 n + 5 2 ;
Then G G G contains a directed cycle of length ℓ \ell ℓ . Moreover, these bounds are best possible.
The rest of the paper is organized as follows. In Section 2, we introduce our notation and several lemmas we will use in the subsequent proofs. In Section 3, we present the extremal constructions for all values of ℓ \ell ℓ . Sections 4 and 5 contain the proofs of Theorems 1.4 and 1.5 , respectively.
Notation and Preliminaries
Notation
A directed graph G G G is a pair ( V ( G ) , E ( G ) ) (V(G), E(G)) ( V ( G ) , E ( G )) , where E ( G ) ⊆ V ( G ) × V ( G ) E(G) \subseteq V(G) \times V(G) E ( G ) ⊆ V ( G ) × V ( G ) . Elements of E ( G ) E(G) E ( G ) are called arcs. When ( u , v ) ∈ E ( G ) (u,v) \in E(G) ( u , v ) ∈ E ( G ) , we say there is an arc from u u u to v v v . We often write u v uv uv instead of ( u , v ) (u,v) ( u , v ) for brevity. In all directed graphs we consider, loops, i.e., arcs of the form v v vv v v , are not allowed.
Oriented graphs are directed graphs with an additional restriction – for u , v ∈ V ( G ) u,v \in V(G) u , v ∈ V ( G ) , if u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) , then v u ∉ E ( G ) vu \notin E(G) v u ∈ / E ( G ) (this in particular implies there are no loops). As we are mostly concerned with oriented graphs, we refer to them simply as graphs whenever this is clear from the context.
In a directed graph, an outneighbor of a vertex v v v is a vertex u u u such that v u vu v u is an arc. Similarly, u u u is an inneighbor of v v v if u v uv uv is an arc.
The outneighborhood N + ( v ) N^{+}(v) N + ( v ) of a vertex v v v is the set of its outneighbors. Symmetrically, the inneighborhood N − ( v ) N^{-}(v) N − ( v ) is the set of the inneighbors of v v v . The outdegree and indegree of v v v are d + ( v ) : = ∣ N + ( v ) ∣ d^{+}(v) := |N^{+}(v)| d + ( v ) := ∣ N + ( v ) ∣ and d − ( v ) : = ∣ N − ( v ) ∣ d^{-}(v) := |N^{-}(v)| d − ( v ) := ∣ N − ( v ) ∣ , respectively. Whenever the underlying graph is not clear from the context, we indicate it by a subscript, writing N G + ( v ) N_G^{+}(v) N G + ( v ) , d G + ( v ) d_G^{+}(v) d G + ( v ) , and so on. Define:
δ + ( G ) = min v ∈ V ( G ) d + ( v ) minimum outdegree Δ + ( G ) = max v ∈ V ( G ) d + ( v ) maximum outdegree δ − ( G ) = min v ∈ V ( G ) d − ( v ) minimum indegree Δ − ( G ) = max v ∈ V ( G ) d − ( v ) maximum indegree δ ± ( G ) = min ( δ + ( G ) , δ − ( G ) ) minimum semidegree \begin{aligned}
\delta^{+}(G) &= \min_{v \in V(G)} d^{+}(v) && \text{minimum outdegree} \\
\Delta^{+}(G) &= \max_{v \in V(G)} d^{+}(v) && \text{maximum outdegree} \\
\delta^{-}(G) &= \min_{v \in V(G)} d^{-}(v) && \text{minimum indegree} \\
\Delta^{-}(G) &= \max_{v \in V(G)} d^{-}(v) && \text{maximum indegree} \\
\delta^{\pm}(G) &= \min(\delta^{+}(G),\delta^{-}(G)) && \text{minimum semidegree}
\end{aligned} δ + ( G ) Δ + ( G ) δ − ( G ) Δ − ( G ) δ ± ( G ) = v ∈ V ( G ) min d + ( v ) = v ∈ V ( G ) max d + ( v ) = v ∈ V ( G ) min d − ( v ) = v ∈ V ( G ) max d − ( v ) = min ( δ + ( G ) , δ − ( G )) minimum outdegree maximum outdegree minimum indegree maximum indegree minimum semidegree
We extend the notion of out- and inneighborhood to sets of vertices – for A ⊆ V ( G ) A \subseteq V(G) A ⊆ V ( G ) , we set N + ( A ) : = ⋃ a ∈ A N + ( a ) N^{+}(A) := \bigcup_{a\in A} N^{+}(a) N + ( A ) := ⋃ a ∈ A N + ( a ) , and define N − ( A ) N^{-}(A) N − ( A ) analogously.
For A , B ⊆ V ( G ) A, B \subseteq V(G) A , B ⊆ V ( G ) , we set E ( A , B ) : = E ( G ) ∩ ( A × B ) E(A,B) := E(G) \cap(A \times B) E ( A , B ) := E ( G ) ∩ ( A × B ) (the set of arcs from A A A to B B B in the graph G G G ) and e ( A , B ) : = ∣ E ( A , B ) ∣ e(A,B) := |E(A,B)| e ( A , B ) := ∣ E ( A , B ) ∣ .
A blow-up of a graph G G G on k k k vertices v 1 , v 2 , … , v k v_1,v_2,\ldots,v_k v 1 , v 2 , … , v k is any graph G ′ G' G ′ whose vertex set is partitioned into sets V 1 , V 2 , … , V k V_1,V_2,\ldots,V_k V 1 , V 2 , … , V k and in which, for all i , j i,j i , j and all u ∈ V i u\in V_i u ∈ V i , v ∈ V j v\in V_j v ∈ V j , there is an arc u v uv uv if and only if there is an arc v i v j v_iv_j v i v j in G G G . The sets V i V_i V i are called blobs ; note that they are independent sets, as G G G has no loops. We sometimes refer to a blow-up of a graph G G G as a G G G -blow-up.
A blow-up is balanced if ∣ ∣ V i ∣ − ∣ V j ∣ ∣ ≤ 1 | |V_i| - |V_j| | \le1 ∣∣ V i ∣ − ∣ V j ∣∣ ≤ 1 for any i , j i,j i , j . Note that for every integer n ≥ k n \ge k n ≥ k there exists a balanced blow-up of G G G on n n n vertices. By G [ t ] G[t] G [ t ] we denote the blow-up of G G G in which ∣ V 1 ∣ = ∣ V 2 ∣ = … = ∣ V k ∣ = t |V_1| = |V_2| = \ldots= |V_k| = t ∣ V 1 ∣ = ∣ V 2 ∣ = … = ∣ V k ∣ = t .
A graph H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) is a subgraph of G = ( V G , E G ) G=(V_G,E_G) G = ( V G , E G ) if V H ⊆ V G V_H \subseteq V_G V H ⊆ V G and E H ⊆ E G E_H \subseteq E_G E H ⊆ E G . The subgraph is spanning if V H = V G V_H=V_G V H = V G . Moreover, we say that H H H is an induced subgraph of G G G if E H = E G ∩ ( V H × V H ) E_H=E_G\cap(V_H\times V_H) E H = E G ∩ ( V H × V H ) . The induced subgraph of G G G on a vertex set V H V_H V H is denoted by G [ V H ] G[V_H] G [ V H ] .
For a graph F F F , we say G G G is F F F -free if G G G does not contain F F F as a subgraph. For a family F \mathcal{F} F of graphs, we say that G G G is F \mathcal{F} F -free if G G G does not contain any element of F \mathcal{F} F as a subgraph.
A graph H H H is homomorphic to a graph F F F if there exists a function ϕ : V ( H ) → V ( F ) \phi:V(H)\to V(F) ϕ : V ( H ) → V ( F ) such that ϕ ( h 1 ) ϕ ( h 2 ) ∈ E ( F ) \phi(h_1)\phi(h_2)\in E(F) ϕ ( h 1 ) ϕ ( h 2 ) ∈ E ( F ) for every arc h 1 h 2 ∈ E ( H ) h_1h_2\in E(H) h 1 h 2 ∈ E ( H ) ; such a function is called a homomorphism from H H H to F F F . Moreover, F F F is a homomorphic image of H H H if there exists a homomorphism ϕ \phi ϕ from H H H to F F F which is surjective and under which every arc of F F F is the image of an arc of H H H ; formally, if for every f 1 f 2 ∈ E ( F ) f_1f_2\in E(F) f 1 f 2 ∈ E ( F ) there is an arc h 1 h 2 ∈ E ( H ) h_1h_2\in E(H) h 1 h 2 ∈ E ( H ) with f 1 = ϕ ( h 1 ) f_1=\phi(h_1) f 1 = ϕ ( h 1 ) and f 2 = ϕ ( h 2 ) f_2=\phi(h_2) f 2 = ϕ ( h 2 ) .
Observe that H H H is a subgraph of F [ t ] F[t] F [ t ] for some t t t if and only if F F F contains a homomorphic image of H H H .
For an integer ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 , by C ⃗ ℓ \vec{C}_{\ell} C ℓ we denote the directed cycle of length ℓ \ell ℓ , that is, the oriented graph with vertices v 1 , v 2 , … , v ℓ v_1,v_2,\ldots,v_\ell v 1 , v 2 , … , v ℓ and arcs v 1 v 2 , v 2 v 3 , … , v ℓ v 1 v_1v_2,v_2v_3,\ldots,v_\ell v_1 v 1 v 2 , v 2 v 3 , … , v ℓ v 1 . We also refer to C ⃗ ℓ \vec{C}_{\ell} C ℓ as the ℓ \ell ℓ -cycle.
A directed walk of length ℓ \ell ℓ is a sequence of not necessarily distinct vertices v 0 , v 1 , … , v ℓ v_0,v_1,\ldots,v_\ell v 0 , v 1 , … , v ℓ such that there are arcs v 0 v 1 , v 1 v 2 , … , v ℓ − 1 v ℓ v_0v_1,v_1v_2,\ldots,v_{\ell-1}v_\ell v 0 v 1 , v 1 v 2 , … , v ℓ − 1 v ℓ . A directed walk is closed if v 0 = v ℓ v_0=v_\ell v 0 = v ℓ . By W ⃗ ℓ \vec{W}_{\ell} W ℓ we denote the family of homomorphic images of C ⃗ ℓ \vec{C}_{\ell} C ℓ . Note that a graph G G G is W ⃗ ℓ \vec{W}_{\ell} W ℓ -free if and only if it does not contain any closed walk of length ℓ \ell ℓ .
A directed path of length ℓ \ell ℓ is an oriented graph P P P on ℓ + 1 \ell+1 ℓ + 1 vertices v 0 , v 1 , … , v ℓ v_0,v_1,\ldots,v_\ell v 0 , v 1 , … , v ℓ with ℓ \ell ℓ arcs v 0 v 1 , v 1 v 2 , … , v ℓ − 1 v ℓ v_0v_1,v_1v_2,\ldots,v_{\ell-1}v_\ell v 0 v 1 , v 1 v 2 , … , v ℓ − 1 v ℓ . We say that such a path starts in v 0 v_0 v 0 and ends in v ℓ v_\ell v ℓ . The vertices v 0 , v ℓ v_0,v_\ell v 0 , v ℓ are called the end vertices of P P P , whereas v 1 , v 2 , … , v ℓ − 1 v_1,v_2,\ldots,v_{\ell-1} v 1 , v 2 , … , v ℓ − 1 are called the internal vertices .
The distance from a vertex a a a to a vertex b b b in an oriented graph G G G is the length of a shortest directed path in G G G which starts in a a a and ends in b b b ; if no such path exists, the distance is infinite.
Frobenius Coin Problem
The Frobenius Coin Problem asks, given a sequence of positive integers ( a 1 , a 2 , … , a m ) (a_1,a_2,\ldots,a_m) ( a 1 , a 2 , … , a m ) (“coin denominations”), for the largest integer N N N which is not expressible in the form x 1 a 1 + x 2 a 2 + … + x m a m x_1a_1+x_2a_2+\ldots+x_ma_m x 1 a 1 + x 2 a 2 + … + x m a m for some nonnegative integers x 1 , x 2 , … , x m x_1,x_2,\ldots,x_m x 1 , x 2 , … , x m . Note that, in order for the problem to be well defined, gcd ( a 1 , a 2 , … , a m ) = 1 \gcd(a_1,a_2,\ldots,a_m)=1 g cd( a 1 , a 2 , … , a m ) = 1 must hold.
We use the following classic result by Sylvester, which solves the m = 2 m=2 m = 2 case.
Proposition 2.1 ([9]). Let a , b a,b a , b be coprime positive integers. If a positive integer ℓ \ell ℓ satisfies ℓ ≥ ( a − 1 ) ( b − 1 ) \ell\ge(a-1)(b-1) ℓ ≥ ( a − 1 ) ( b − 1 ) , then ℓ \ell ℓ can be represented as x a + y b xa+yb x a + y b , where x , y x,y x , y are nonnegative integers.
In our applications we need the following, slightly generalized, form.
Corollary 2.2. Let a , b , ℓ a,b,\ell a , b , ℓ be positive integers such that gcd ( a , b ) ∣ ℓ \gcd(a,b)\mid\ell g cd( a , b ) ∣ ℓ . If ℓ ≥ ( a − 1 ) ( b − 1 ) gcd ( a , b ) \ell\ge\frac{(a-1)(b-1)}{\gcd(a,b)} ℓ ≥ g c d ( a , b ) ( a − 1 ) ( b − 1 ) , then ℓ \ell ℓ can be represented as x a + y b xa+yb x a + y b , where x , y x,y x , y are nonnegative integers.
Proof. Let d = gcd ( a , b ) d=\gcd(a,b) d = g cd( a , b ) and define a ′ = a d a'=\frac{a}{d} a ′ = d a , b ′ = b d b'=\frac{b}{d} b ′ = d b and ℓ ′ = ℓ d \ell'=\frac{\ell}{d} ℓ ′ = d ℓ . Then a ′ , b ′ , ℓ ′ a',b',\ell' a ′ , b ′ , ℓ ′ are positive integers, gcd ( a ′ , b ′ ) = 1 \gcd(a',b')=1 g cd( a ′ , b ′ ) = 1 , and
d ( a ′ − 1 ) ( b ′ − 1 ) ≤ 1 d ( d a ′ − 1 ) ( d b ′ − 1 ) = 1 d ( a − 1 ) ( b − 1 ) ≤ ℓ , d(a'-1)(b'-1)\le\frac{1}{d}(da'-1)(db'-1)=\frac{1}{d}(a-1)(b-1)\le\ell, d ( a ′ − 1 ) ( b ′ − 1 ) ≤ d 1 ( d a ′ − 1 ) ( d b ′ − 1 ) = d 1 ( a − 1 ) ( b − 1 ) ≤ ℓ ,
so that ℓ ′ ≥ ( a ′ − 1 ) ( b ′ − 1 ) \ell'\ge(a'-1)(b'-1) ℓ ′ ≥ ( a ′ − 1 ) ( b ′ − 1 ) . By Proposition 2.1, ℓ ′ = x a ′ + y b ′ \ell'=xa'+yb' ℓ ′ = x a ′ + y b ′ for some nonnegative integers x , y x,y x , y , and thus ℓ = x a + y b \ell=xa+yb ℓ = x a + y b .
Sumsets
We are going to operate on sets of remainders modulo k k k . For A , B ⊆ Z k A,B\subseteq\mathbb{Z}_k A , B ⊆ Z k , define
A + B : = { a + b m o d k : a ∈ A , b ∈ B } . A+B:=\{a+b\bmod k:a\in A,b\in B\}. A + B := { a + b mod k : a ∈ A , b ∈ B } .
Given a family of sets of remainders A 1 , A 2 , … , A m ⊆ Z k A_1,A_2,\ldots,A_m\subseteq\mathbb{Z}_k A 1 , A 2 , … , A m ⊆ Z k , our aim is to compose the special remainder ℓ m o d k \ell\bmod k ℓ mod k using at most one remainder from each of the sets A i A_i A i . To put this formally, we ask whether ( ℓ m o d k ) ∈ ( A 1 ∪ { 0 } ) + … + ( A m ∪ { 0 } ) (\ell\bmod k)\in(A_1\cup\{0\})+\ldots+(A_m\cup\{0\}) ( ℓ mod k ) ∈ ( A 1 ∪ { 0 }) + … + ( A m ∪ { 0 }) . Define
C ( A 1 , A 2 , … , A m ) : = ( ( A 1 ∪ { 0 } ) + … + ( A m ∪ { 0 } ) ) ∖ { 0 } C(A_1,A_2,\ldots,A_m):=((A_1\cup\{0\})+\ldots+(A_m\cup\{0\}))\setminus\{0\} C ( A 1 , A 2 , … , A m ) := (( A 1 ∪ { 0 }) + … + ( A m ∪ { 0 })) ∖ { 0 }
to be the set of “composable” non-zero remainders modulo k k k .
We quote the following two results from [4 ] . Even though they were initially stated for ℓ \ell ℓ divisible by 12, generalizing to ℓ \ell ℓ divisible by 6 is immediate.
Lemma 2.3 ([4]). Let ℓ \ell ℓ be a multiple of 6, let k k k be the smallest integer that does not divide ℓ \ell ℓ , and let A 1 , … , A m A_1,\ldots,A_m A 1 , … , A m be a collection of m m m sets of non-zero remainders modulo k k k . If ℓ m o d k \ell\bmod k ℓ mod k does not belong to C ( A 1 , … , A m ) C(A_1,\ldots,A_m) C ( A 1 , … , A m ) , then ∣ C ( A 1 , … , A m ) ∣ ≥ ∣ A 1 ∣ + … + ∣ A m ∣ |C(A_1,\ldots,A_m)|\ge|A_1|+\ldots+|A_m| ∣ C ( A 1 , … , A m ) ∣ ≥ ∣ A 1 ∣ + … + ∣ A m ∣ .
In particular, if ∣ A 1 ∣ + … + ∣ A m ∣ ≥ k − 1 |A_1|+\ldots+|A_m|\ge k-1 ∣ A 1 ∣ + … + ∣ A m ∣ ≥ k − 1 , then ℓ m o d k ∈ C ( A 1 , … , A m ) \ell\bmod k\in C(A_1,\ldots,A_m) ℓ mod k ∈ C ( A 1 , … , A m ) .
Considering the special case in which every set A i A_i A i has exactly one element leads to the following corollary.
Corollary 2.4 ([4]). Let ℓ \ell ℓ be a multiple of 6 and let k k k be the smallest integer that does not divide ℓ \ell ℓ . If S S S is a multiset of k − 1 k-1 k − 1 non-zero remainders modulo k k k , then there exists a sub-multiset S ′ ⊆ S S'\subseteq S S ′ ⊆ S such that
ℓ ≡ ∑ x ∈ S ′ x ( m o d k ) . \ell\equiv\sum_{x\in S'}x\pmod k. ℓ ≡ x ∈ S ′ ∑ x ( mod k ) .
Szemerédi Regularity Lemma
Lastly, we will use the following proposition, which is a standard application of the Szemerédi Regularity Lemma for directed graphs [1 ] .
Proposition 2.5. Let ℓ ≥ 4 \ell\ge4 ℓ ≥ 4 be an integer and let ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . There exists n 0 = n 0 ( ℓ , ε ) n_0=n_0(\ell,\varepsilon) n 0 = n 0 ( ℓ , ε ) with the following property. If G G G is a C → ℓ \overrightarrow{C}_{\ell} C ℓ -free oriented graph on n ≥ n 0 n\ge n_0 n ≥ n 0 vertices, then G G G contains a W → ℓ \overrightarrow{W}_{\ell} W ℓ -free subgraph H H H on at least ( 1 − ε ) n (1-\varepsilon)n ( 1 − ε ) n vertices such that d H + ( v ) ≥ d G + ( v ) − ε n d_H^+(v)\ge d_G^+(v)-\varepsilon n d H + ( v ) ≥ d G + ( v ) − ε n for each v ∈ V ( H ) v\in V(H) v ∈ V ( H ) .
In particular, if an n n n -vertex oriented graph G G G is C → ℓ \overrightarrow{C}_{\ell} C ℓ -free, then one can remove o ( n ) o(n) o ( n ) vertices and o ( n 2 ) o(n^2) o ( n 2 ) arcs from G G G to obtain a W → ℓ \overrightarrow{W}_{\ell} W ℓ -free subgraph H H H with δ + ( H ) ≥ δ + ( G ) − o ( n ) \delta^+(H)\ge\delta^+(G)-o(n) δ + ( H ) ≥ δ + ( G ) − o ( n ) .
Constructions
We now present the best known extremal constructions. Recall that k k k denotes the smallest integer greater than 2 that does not divide ℓ \ell ℓ . Our first aim is to construct arbitrarily large C → ℓ \overrightarrow{C}_{\ell} C ℓ -free graphs G G G on n n n vertices with δ + ( G ) = n k + k − 2 k \delta^{+}(G)=\frac{n}{k}+\frac{k-2}{k} δ + ( G ) = k n + k k − 2 , which shows that the outdegree bound in Theorem 1.4 cannot be lowered.
To this end, take n ≡ 2 ( m o d k ) n\equiv2\pmod{k} n ≡ 2 ( mod k ) and consider the balanced blow-up G 0 G_{0} G 0 of C → k \overrightarrow{C}_{k} C k on n + k − 2 n+k-2 n + k − 2 vertices; all its blobs are then of the same size n + k − 2 k \frac{n+k-2}{k} k n + k − 2 . Since every cycle in a C → k \overrightarrow{C}_{k} C k -blow-up has length divisible by k k k , and k k k does not divide ℓ \ell ℓ , the graph G 0 G_{0} G 0 contains no C → ℓ \overrightarrow{C}_{\ell} C ℓ . Moreover, δ + ( G 0 ) = n + k − 2 k = n k + k − 2 k \delta^{+}(G_{0})=\frac{n+k-2}{k}=\frac{n}{k}+\frac{k-2}{k} δ + ( G 0 ) = k n + k − 2 = k n + k k − 2 .
The goal is to decrease the number of vertices to n n n while preserving the minimum outdegree and the C → ℓ \overrightarrow{C}_{\ell} C ℓ -freeness of our construction. We do this iteratively, by building a sequence of k − 1 k-1 k − 1 graphs, G 0 , G 1 , … , G k − 2 G_{0},G_{1},\ldots,G_{k-2} G 0 , G 1 , … , G k − 2 . Denote
R i = { r ∈ Z k : G i contains C → m for some m ≡ r ( m o d k ) } . R_i=\{r\in\mathbb{Z}_k:G_i\text{ contains }\overrightarrow{C}_m\text{ for some }m\equiv r\pmod{k}\}. R i = { r ∈ Z k : G i contains C m for some m ≡ r ( mod k )} .
Clearly, R 0 = { 0 } R_0=\{0\} R 0 = { 0 } . In each step of our construction we ensure that:
δ + ( G i + 1 ) = δ + ( G i ) \delta^{+}(G_{i+1})=\delta^{+}(G_i) δ + ( G i + 1 ) = δ + ( G i ) ;
∣ V ( G i + 1 ) ∣ = ∣ V ( G i ) ∣ − 1 |V(G_{i+1})|=|V(G_i)|-1 ∣ V ( G i + 1 ) ∣ = ∣ V ( G i ) ∣ − 1 ;
∣ R i + 1 ∣ = ∣ R i ∣ + 1 |R_{i+1}|=|R_i|+1 ∣ R i + 1 ∣ = ∣ R i ∣ + 1 .
At the end we will obtain a graph G k − 2 G_{k-2} G k − 2 on n n n vertices with δ + ( G k − 2 ) = δ + ( G 0 ) = n k + k − 2 k \delta^{+}(G_{k-2})=\delta^{+}(G_0)=\frac{n}{k}+\frac{k-2}{k} δ + ( G k − 2 ) = δ + ( G 0 ) = k n + k k − 2 . We aim to have R k − 2 = Z k ∖ { ℓ ( m o d k ) } R_{k-2}=\mathbb{Z}_k\setminus\{\ell\pmod{k}\} R k − 2 = Z k ∖ { ℓ ( mod k )} , which will make G k − 2 G_{k-2} G k − 2 the desired extremal construction.
Since we only remove vertices and add arcs in our process, each vertex in the graphs G i G_i G i has a unique blob of the initial C → k \overrightarrow{C}_k C k -blow-up G 0 G_0 G 0 associated with it. Refer to these blobs as V 1 , … , V k V_1,\ldots,V_k V 1 , … , V k , with indices taken modulo k k k . For each r ∈ { 3 , 4 , … , k − 1 } r\in\{3,4,\ldots,k-1\} r ∈ { 3 , 4 , … , k − 1 } , we define an r r r -maneuver as follows:
pick a special vertex v v v , which was not chosen before, from a blob V j V_j V j such that no vertex of V j + r − 1 V_{j+r-1} V j + r − 1 is an outneighbor of v v v ;
add arcs from all vertices in V j + r − 1 V_{j+r-1} V j + r − 1 to the special vertex v v v ;
delete a vertex (which was not special in any of the previous maneuvers) from V j + r V_{j+r} V j + r .
See Figure 1 for an example. The restriction on the blob V j V_j V j guarantees that G i + 1 G_{i+1} G i + 1 is again an oriented graph, that is, that the added arcs do not create a symmetric pair. Since each maneuver excludes at most one of the k k k blobs, an admissible blob always exists. Note also that the values r ≤ 2 r\leq2 r ≤ 2 are not allowed, since the added arcs would create a loop (for r = 1 r=1 r = 1 ) or a symmetric pair (for r = 2 r=2 r = 2 ).
Figure 1. Example of a 4-maneuver for k = 7 k=7 k = 7 .
It is straightforward to see that Properties 1 and 2 are preserved. Indeed, deleting a vertex of V j + r V_{j+r} V j + r decreases the outdegree of every vertex of V j + r − 1 V_{j+r-1} V j + r − 1 by one, which is exactly compensated by the arcs added to v v v , while all the remaining outdegrees are unchanged; here we use that the deleted vertex is not special, and hence its only inneighbors are the vertices of V j + r − 1 V_{j+r-1} V j + r − 1 . Moreover, if G i + 1 G_{i+1} G i + 1 was obtained from G i G_i G i through an r r r -maneuver, then R i + 1 = R i + { 0 , r } R_{i+1}=R_i+\{0,r\} R i + 1 = R i + { 0 , r } , as we can use the special vertex to make one shortcut and return to the starting blob after r r r steps rather than k k k . Observe that if in each step we apply either an r r r -maneuver or a ( k − r ) (k-r) ( k − r ) -maneuver for a fixed r r r coprime with k k k , then Property 3 holds.
We will now describe constructions (i.e. choices of maneuvers) for various ℓ \ell ℓ . We start with the case k ≥ 7 k \ge7 k ≥ 7 .
For odd k k k , take r = k − 1 2 r = \frac{k-1}{2} r = 2 k − 1 . Since 2 r ≡ − 1 ( m o d k ) 2r \equiv-1 \pmod{k} 2 r ≡ − 1 ( mod k ) , the number r r r is coprime with k k k , and so there exists a ∈ { 1 , 2 , … , k − 1 } a \in\{1,2,\ldots,k-1\} a ∈ { 1 , 2 , … , k − 1 } such that a r ≡ ℓ ( m o d k ) ar \equiv\ell\pmod{k} a r ≡ ℓ ( mod k ) ; note that a ≠ 0 a \ne0 a = 0 , as k k k does not divide ℓ \ell ℓ . Now, perform ( a − 1 ) (a-1) ( a − 1 ) times an r r r -maneuver and ( k − a − 1 ) (k-a-1) ( k − a − 1 ) times a ( k − r ) (k-r) ( k − r ) -maneuver. Altogether this makes k − 2 k-2 k − 2 maneuvers, and since a ( k − r ) (k-r) ( k − r ) -maneuver contributes the remainder − r -r − r , we end up with
R k − 2 = { c r m o d k : − ( k − a − 1 ) ≤ c ≤ a − 1 } = Z k ∖ { ℓ m o d k } , R_{k-2}=\{cr \bmod k : -(k-a-1)\le c\le a-1\}=\mathbb{Z}_k\setminus\{\ell\bmod k\}, R k − 2 = { cr mod k : − ( k − a − 1 ) ≤ c ≤ a − 1 } = Z k ∖ { ℓ mod k } ,
because a a a is the only remainder modulo k k k missing from the above range of c c c .
For even k k k , recall that k k k is always a prime power, so k = 2 s k=2^s k = 2 s for some integer s ≥ 3 s\ge3 s ≥ 3 . Therefore, r = 3 r=3 r = 3 is coprime with k k k , and we may proceed as above: we take a a a such that 3 a ≡ ℓ ( m o d k ) 3a\equiv\ell\pmod{k} 3 a ≡ ℓ ( mod k ) and apply ( a − 1 ) (a-1) ( a − 1 ) times a 3-maneuver and ( k − a − 1 ) (k-a-1) ( k − a − 1 ) times a ( k − 3 ) (k-3) ( k − 3 ) -maneuver.
For k = 5 k=5 k = 5 , only 3- and 4-maneuvers are available, and there is no r r r for which both an r r r -maneuver and a ( k − r ) (k-r) ( k − r ) -maneuver could be used. Therefore, we cannot use the same method as above. Table 1 lists the best possible constructions with the available maneuvers. Here, as in the general construction, we assume that n n n is such that k k k divides the number of vertices of the initial blow-up; the same applies to Table 2 below.
Table 1. Best known constructions for k = 5 k=5 k = 5 .
Table 2. Best known constructions for k = 4 k=4 k = 4 .
For k = 4 k=4 k = 4 , we are limited to 3-maneuvers, resulting in the constructions in Table 2. By Theorems 1.4 and 1.5 , these constructions are best possible for large enough cycles. We believe that they are best possible for small cycles as well.
Proof of Theorem 1.4
The first main step of the proof of Theorem 1.4 is to show that any C ⃗ ℓ \vec{C}_{\ell} C ℓ -free oriented graph G G G on n n n vertices with δ + ( G ) > n k \delta^{+}(G) > \frac{n}{k} δ + ( G ) > k n contains a subgraph H H H homomorphic to C ⃗ k \vec{C}_{k} C k having semidegree δ ± ( H ) ≥ n k − o ( n ) \delta^{\pm}(H) \ge\frac{n}{k} - o(n) δ ± ( H ) ≥ k n − o ( n ) . This reasoning is split into two cases based on the parity of ℓ \ell ℓ in the next two subsections. The second step is to determine more structure of G G G by using the outdegree bound on G G G and the semidegree bound on H H H , in particular proving that one can assume that H H H is an induced subgraph of G G G . This is done in Subsection 4.3, where we introduce useful notation and prove observations that will be also useful in the later proof of Theorem 1.5. The conclusion of the proof of Theorem 1.4 is in Subsection 4.4 and contains the only place where the exact bound δ + ( G ) ≥ n k + k − 1 k \delta^{+}(G) \ge\frac{n}{k}+\frac{k-1}{k} δ + ( G ) ≥ k n + k k − 1 is used.
In the proofs that follow, we use the following approximate result towards the Caccetta–Häggkvist conjecture, proved in [4 ] .
Lemma 4.1 ([4 ] ). Let m m m be a positive integer. Every oriented graph F F F on N N N vertices with δ + ( F ) ≥ ( 1 − 0.65351 1 / m ) N \delta^{+}(F) \ge(1-0.65351^{1/m})N δ + ( F ) ≥ ( 1 − 0.6535 1 1/ m ) N contains a directed cycle of length at most 3 m 3m 3 m .
Approximate structure in the even case
The objective of this section is proving the following lemma.
Lemma 4.2. Let ℓ \ell ℓ be an integer divisible by 6 and denote by k k k the smallest integer greater than 2 which does not divide ℓ \ell ℓ . If ℓ > 20 k 2 \ell> 20k^{2} ℓ > 20 k 2 , then every C ⃗ ℓ \vec{C}_{\ell} C ℓ -free oriented graph G G G on n n n vertices with δ + ( G ) > n k \delta^{+}(G) > \frac{n}{k} δ + ( G ) > k n contains a subgraph H H H homomorphic to C ⃗ k \vec{C}_{k} C k with δ ± ( H ) ≥ n k − o ( n ) \delta^{\pm}(H) \ge\frac{n}{k}-o(n) δ ± ( H ) ≥ k n − o ( n ) .
Proof. Apply Proposition 2.5 to the graph G G G to obtain a W ⃗ ℓ \vec{W}_{\ell} W ℓ -free subgraph H H H with δ + ( H ) ≥ n k − o ( n ) \delta^{+}(H) \ge\frac{n}{k}-o(n) δ + ( H ) ≥ k n − o ( n ) . We will show that after removing o ( n ) o(n) o ( n ) vertices from H H H , we obtain the desired graph.
Note that, by the minimality of k k k , every integer smaller than k k k divides ℓ \ell ℓ . In particular, if H H H contained a directed cycle of length p ≤ k − 1 p \le k-1 p ≤ k − 1 , then p ≥ 3 p \ge3 p ≥ 3 and p ∣ ℓ p \mid\ell p ∣ ℓ , so traversing this cycle ℓ p \frac{\ell}{p} p ℓ times would give a closed walk of length ℓ \ell ℓ in H H H , contradicting its W ⃗ ℓ \vec{W}_{\ell} W ℓ -freeness. We use this observation repeatedly.
We start with the following claim, that resembles [4 Claim 4.1] and will allow us to build directed cycles. In contrast to [4 Claim 4.1] , we do not have an indegree assumption, thus we cannot claim existence of a short directed path between any two vertices, but only of a short directed path from every vertex to one particularly chosen special vertex.
Claim 4.3. There is a vertex v 0 ∈ V ( H ) v_0 \in V(H) v 0 ∈ V ( H ) such that for every v ∈ V ( H ) v \in V(H) v ∈ V ( H ) , there is a directed path of length at most 10 ⌊ k − 1 3 ⌋ 10\left\lfloor\frac{k-1}{3}\right\rfloor 10 ⌊ 3 k − 1 ⌋ from v v v to v 0 v_0 v 0 .
Proof. Let m : = ⌊ k − 1 3 ⌋ m := \left\lfloor\frac{k-1}{3} \right\rfloor m := ⌊ 3 k − 1 ⌋ , c : = 1 − 0.6535 1 / m c := 1 - 0.6535^{1/m} c := 1 − 0.653 5 1/ m . Take any vertex v ∈ V ( H ) v \in V(H) v ∈ V ( H ) . We define X 1 : = N + ( v ) X_1 := N^{+}(v) X 1 := N + ( v ) and X i : = X i − 1 ∪ N + ( X i − 1 ) X_i := X_{i-1} \cup N^{+}(X_{i-1}) X i := X i − 1 ∪ N + ( X i − 1 ) for every i ∈ { 2 , … , 5 m } i \in\{2,\ldots,5m\} i ∈ { 2 , … , 5 m } . Observe that for each i ∈ { 2 , … , 5 m } i \in\{2,\ldots,5m\} i ∈ { 2 , … , 5 m } , the induced graph H [ X i − 1 ] H[X_{i-1}] H [ X i − 1 ] cannot contain a directed cycle of length at most 3 m ≤ k − 1 3m \le k-1 3 m ≤ k − 1 , as otherwise H H H would contain a closed walk of length ℓ \ell ℓ . Therefore, δ + ( H [ X i − 1 ] ) < c ∣ X i − 1 ∣ \delta^{+}(H[X_{i-1}]) < c|X_{i-1}| δ + ( H [ X i − 1 ]) < c ∣ X i − 1 ∣ by Lemma 4.1, meaning there is a vertex u ∈ X i − 1 u \in X_{i-1} u ∈ X i − 1 with more than δ + ( H ) − c ∣ X i − 1 ∣ \delta^{+}(H)-c|X_{i-1}| δ + ( H ) − c ∣ X i − 1 ∣ outneighbours outside of X i − 1 X_{i-1} X i − 1 , so
∣ X i ∣ > δ + ( H ) + ( 1 − c ) ∣ X i − 1 ∣ . |X_i| > \delta^{+}(H) + (1-c)|X_{i-1}|. ∣ X i ∣ > δ + ( H ) + ( 1 − c ) ∣ X i − 1 ∣.
This, by induction on i i i and ∣ X 1 ∣ ≥ δ + ( H ) |X_1| \ge\delta^{+}(H) ∣ X 1 ∣ ≥ δ + ( H ) , gives
∣ X i ∣ ≥ δ + ( H ) ⋅ 1 − ( 1 − c ) i c = δ + ( H ) ⋅ 1 − 0.6535 i / m 1 − 0.6535 1 / m . |X_i| \ge\delta^{+}(H) \cdot\frac{1-(1-c)^i}{c} = \delta^{+}(H) \cdot\frac{1-0.6535^{i/m}}{1-0.6535^{1/m}}. ∣ X i ∣ ≥ δ + ( H ) ⋅ c 1 − ( 1 − c ) i = δ + ( H ) ⋅ 1 − 0.653 5 1/ m 1 − 0.653 5 i / m .
In particular,
∣ X 5 m ∣ ≥ δ + ( H ) ⋅ 1 − 0.6535 5 1 − 0.6535 1 / m = n k ⋅ 1 − 0.6535 5 1 − 0.6535 1 / m − o ( n ) . |X_{5m}| \ge\delta^{+}(H) \cdot\frac{1-0.6535^5}{1-0.6535^{1/m}} = \frac{n}{k} \cdot\frac{1-0.6535^5}{1-0.6535^{1/m}} - o(n). ∣ X 5 m ∣ ≥ δ + ( H ) ⋅ 1 − 0.653 5 1/ m 1 − 0.653 5 5 = k n ⋅ 1 − 0.653 5 1/ m 1 − 0.653 5 5 − o ( n ) .
We will show that for each k k k , ∣ X 5 m ∣ > 1 2 n |X_{5m}| > \frac{1}{2}n ∣ X 5 m ∣ > 2 1 n . Since m = ⌊ k − 1 3 ⌋ m = \left\lfloor\frac{k-1}{3} \right\rfloor m = ⌊ 3 k − 1 ⌋ , we have k = 3 m + r k=3m+r k = 3 m + r with r ∈ { 1 , 2 , 3 } r\in\{1,2,3\} r ∈ { 1 , 2 , 3 } . Consider the function
f ( m ) = 1 3 m + r ⋅ 1 − 0.6535 5 1 − 0.6535 1 / m . f(m)=\frac{1}{3m+r}\cdot\frac{1-0.6535^5}{1-0.6535^{1/m}}. f ( m ) = 3 m + r 1 ⋅ 1 − 0.653 5 1/ m 1 − 0.653 5 5 .
By computing the derivative, one can verify that this function is increasing in m m m for m ≥ 1 m \ge1 m ≥ 1 . Thus, in order to prove that ∣ X 5 m ∣ > 1 2 n |X_{5m}| > \frac{1}{2}n ∣ X 5 m ∣ > 2 1 n for each k k k , it is enough to check it for the smallest possible values of k k k with different remainders modulo 3. For k = 4 k=4 k = 4 we have ∣ X 5 m ∣ ≥ 0.635 n − o ( n ) |X_{5m}| \ge0.635n-o(n) ∣ X 5 m ∣ ≥ 0.635 n − o ( n ) , for k = 5 k=5 k = 5 , ∣ X 5 m ∣ ≥ 0.508 n − o ( n ) |X_{5m}| \ge0.508n-o(n) ∣ X 5 m ∣ ≥ 0.508 n − o ( n ) , while if 3 ∣ k 3\mid k 3 ∣ k , then k ≥ 9 k\ge9 k ≥ 9 since k k k must be a prime power, and ∣ X 5 m ∣ ≥ 0.510 n − o ( n ) |X_{5m}| \ge0.510n-o(n) ∣ X 5 m ∣ ≥ 0.510 n − o ( n ) . In each case, ∣ X 5 m ∣ > 1 2 n |X_{5m}| > \frac{1}{2}n ∣ X 5 m ∣ > 2 1 n for large enough n n n .
Therefore, for any vertex v v v , there is a directed path of length at most 5 m 5m 5 m from v v v to over a half of the other vertices. This implies there has to be a vertex v 0 v_0 v 0 to which there are paths of length at most 5 m 5m 5 m from more than half of V ( H ) V(H) V ( H ) .
Since the set of vertices to which there is a path of length at most 5 m 5m 5 m from any vertex v v v is larger than 1 2 ∣ V ( H ) ∣ \frac{1}{2}|V(H)| 2 1 ∣ V ( H ) ∣ , and the set of vertices from which there is a path of length at most 5 m 5m 5 m to v 0 v_0 v 0 is larger than 1 2 ∣ V ( H ) ∣ \frac{1}{2}|V(H)| 2 1 ∣ V ( H ) ∣ , their intersection is nonempty; concatenating the two paths through a common vertex we obtain a directed walk, and hence also a directed path, of length at most 10 m 10m 10 m from v v v to v 0 v_0 v 0 , which concludes the proof.
Take the vertex v 0 ∈ V ( H ) v_0 \in V(H) v 0 ∈ V ( H ) from Claim 4.3 and define
V 1 : = N + ( v 0 ) , V_1 := N^{+}(v_0), V 1 := N + ( v 0 ) ,
V i : = N + ( V i − 1 ) ∖ ( ⋃ j < i V j ) for i = 2 , 3 , … , k . V_i := N^{+}(V_{i-1}) \setminus\left(\bigcup_{j<i} V_j\right) \quad\text{for } i=2,3,\ldots,k. V i := N + ( V i − 1 ) ∖ ( j < i ⋃ V j ) for i = 2 , 3 , … , k .
In other words, for i < k i<k i < k , V i V_i V i is the set of vertices at distance exactly i i i from v 0 v_0 v 0 , while V k V_k V k consists of the vertices at distance exactly k k k from v 0 v_0 v 0 and possibly of v 0 v_0 v 0 itself (note that v 0 v_0 v 0 cannot lie in V j V_j V j for j < k j<k j < k , as this would give a closed walk of length j ≤ k − 1 j\le k-1 j ≤ k − 1 ).
Claim 4.4. There are no arcs from V i V_i V i to V j V_j V j in H H H unless j ≡ i + 1 ( m o d k ) j\equiv i+1\pmod{k} j ≡ i + 1 ( mod k ) .
Proof. Denote D : = 10 ⌊ k − 1 3 ⌋ D:=10^{\left\lfloor\frac{k-1}{3}\right\rfloor} D := 1 0 ⌊ 3 k − 1 ⌋ . If there was an arc x y xy x y with x ∈ V i x\in V_i x ∈ V i , y ∈ V j y\in V_j y ∈ V j , then there would be paths of lengths j j j and i + 1 i+1 i + 1 from v 0 v_0 v 0 to y y y . As there is a directed path of length d ≤ D d\le D d ≤ D from y y y to v 0 v_0 v 0 , we obtain intersecting closed directed walks of lengths d + i + 1 d+i+1 d + i + 1 and d + j d+j d + j passing through v 0 v_0 v 0 . Unless j ≡ i + 1 ( m o d k ) j\equiv i+1\pmod{k} j ≡ i + 1 ( mod k ) , we have 1 ≤ ∣ i + 1 − j ∣ ≤ k − 1 1\le|i+1-j|\le k-1 1 ≤ ∣ i + 1 − j ∣ ≤ k − 1 , so gcd ( d + i + 1 , d + j ) ≤ ∣ i + 1 − j ∣ < k \gcd(d+i+1,d+j)\le|i+1-j|<k g cd( d + i + 1 , d + j ) ≤ ∣ i + 1 − j ∣ < k and hence gcd ( d + i + 1 , d + j ) ∣ ℓ \gcd(d+i+1,d+j)\mid\ell g cd( d + i + 1 , d + j ) ∣ ℓ , as every integer smaller than k k k divides ℓ \ell ℓ . Since
ℓ > 20 k 2 > ( ( D + k + 1 ) − 1 ) ( ( D + k ) − 1 ) ≥ ( ( d + i + 1 ) − 1 ) ( d + j − 1 ) , \ell>20k^2>((D+k+1)-1)((D+k)-1)\ge((d+i+1)-1)(d+j-1), ℓ > 20 k 2 > (( D + k + 1 ) − 1 ) (( D + k ) − 1 ) ≥ (( d + i + 1 ) − 1 ) ( d + j − 1 ) ,
ℓ \ell ℓ is representable as x ( d + i + 1 ) + y ( d + j ) x(d+i+1)+y(d+j) x ( d + i + 1 ) + y ( d + j ) with x , y x,y x , y nonnegative integers (Corollary 2.2), and traversing the two closed walks x x x and y y y times, respectively, a forbidden member of W → ℓ \overrightarrow{W}_{\ell} W ℓ is obtained.
As a result, we obtain k k k sets, V 1 , … , V k V_1,\ldots,V_k V 1 , … , V k , each of which forms an independent set in H H H . Moreover, ∣ V 1 ∣ = d + ( v 0 ) ≥ δ + ( H ) |V_1|=d^+(v_0)\ge\delta^+(H) ∣ V 1 ∣ = d + ( v 0 ) ≥ δ + ( H ) and for i = 2 , 3 , … , k i=2,3,\ldots,k i = 2 , 3 , … , k , ∣ V i ∣ ≥ δ + ( H ) ≥ n k − o ( n ) |V_i|\ge\delta^+(H)\ge\frac{n}{k}-o(n) ∣ V i ∣ ≥ δ + ( H ) ≥ k n − o ( n ) , since by Claim 4.4 all outneighbors of a vertex of V i − 1 V_{i-1} V i − 1 lie in V i V_i V i . Let V ′ : = V 1 ∪ ⋯ ∪ V k V':=V_1\cup\cdots\cup V_k V ′ := V 1 ∪ ⋯ ∪ V k . Then ∣ V ′ ∣ ≥ n − o ( n ) |V'|\ge n-o(n) ∣ V ′ ∣ ≥ n − o ( n ) .
The graph H [ V ′ ] H[V'] H [ V ′ ] is homomorphic to C → k \overrightarrow{C}_k C k as needed, but it does not necessarily satisfy δ ± ( H [ V ′ ] ) ≥ n k − o ( n ) \delta^\pm(H[V'])\ge\frac{n}{k}-o(n) δ ± ( H [ V ′ ]) ≥ k n − o ( n ) yet. To achieve this, we have to remove some vertices from V ′ V' V ′ .
Claim 4.5. For any ε > 0 \varepsilon>0 ε > 0 there exists ε 1 > 0 \varepsilon_1>0 ε 1 > 0 such that when δ + ( H ) ≥ n k ( 1 − ε 1 ) \delta^+(H)\ge\frac{n}{k}(1-\varepsilon_1) δ + ( H ) ≥ k n ( 1 − ε 1 ) , then one can remove at most ε n \varepsilon n ε n vertices from V ′ V' V ′ so that the subgraph of H H H induced by the remaining vertices has minimum semidegree at least n k ( 1 − ε ) \frac{n}{k}(1-\varepsilon) k n ( 1 − ε ) . In other words, one can remove o ( n ) o(n) o ( n ) vertices from V ′ V' V ′ so that the obtained induced subgraph has minimum semidegree at least n k − o ( n ) \frac{n}{k}-o(n) k n − o ( n ) .
Proof. Set ε 1 : = ( ε 4 k ) 2 \varepsilon_1:=\left(\frac{\varepsilon}{4k}\right)^2 ε 1 := ( 4 k ε ) 2 and assume that δ + ( H ) ≥ n k ( 1 − ε 1 ) \delta^+(H)\ge\frac{n}{k}(1-\varepsilon_1) δ + ( H ) ≥ k n ( 1 − ε 1 ) . Note that every vertex v ∈ V ( H ) v\in V(H) v ∈ V ( H ) has inneighbors in at most one of the sets V i V_i V i . To see this, let i i i be the smallest index such that v v v has an inneighbor in V i V_i V i . If i = k i=k i = k , then v v v has inneighbors only in V k V_k V k , while if i ≤ k − 1 i\le k-1 i ≤ k − 1 , then v ∈ V i + 1 v\in V_{i+1} v ∈ V i + 1 , and by Claim 4.4 vertices from V i + 1 V_{i+1} V i + 1 cannot have inneighbors in V j V_j V j for j ≠ i j\ne i j = i .
Since each V i V_i V i is of size at least δ + ( H ) \delta^+(H) δ + ( H ) and every v ∈ V ( H ) v\in V(H) v ∈ V ( H ) can have inneighbors in at most one such set,
Δ − ( H ) ≤ n − ( k − 1 ) ⋅ δ + ( H ) ≤ δ + ( H ) + ε 1 n . \Delta^-(H)\le n-(k-1)\cdot\delta^+(H)\le\delta^+(H)+\varepsilon_1n. Δ − ( H ) ≤ n − ( k − 1 ) ⋅ δ + ( H ) ≤ δ + ( H ) + ε 1 n .
Set c : = 1 ε 1 − 1 c:=\frac{1}{\sqrt{\varepsilon_1}}-1 c := ε 1 1 − 1 and partition V ( H ) V(H) V ( H ) based on indegree in H H H :
V l o w = { v ∈ V ( H ) : d − ( v ) ≤ δ + ( H ) − c ε 1 n } , V_{\mathrm{low}}=\{v\in V(H):d^-(v)\le\delta^+(H)-c\varepsilon_1n\}, V low = { v ∈ V ( H ) : d − ( v ) ≤ δ + ( H ) − c ε 1 n } ,
V h i g h = { v ∈ V ( H ) : d − ( v ) > δ + ( H ) − c ε 1 n } . V_{\mathrm{high}}=\{v\in V(H):d^-(v)>\delta^+(H)-c\varepsilon_1n\}. V high = { v ∈ V ( H ) : d − ( v ) > δ + ( H ) − c ε 1 n } .
Then,
∣ V ( H ) ∣ δ + ( H ) ≤ ∑ v ∈ V ( H ) d + ( v ) = ∑ v ∈ V ( H ) d − ( v ) = ∑ v ∈ V l o w d − ( v ) + ∑ v ∈ V h i g h d − ( v ) ≤ ∣ V l o w ∣ ⋅ ( δ + ( H ) − c ε 1 n ) + ∣ V h i g h ∣ ⋅ Δ − ( H ) ≤ ∣ V l o w ∣ ⋅ ( δ + ( H ) − c ε 1 n ) + ∣ V h i g h ∣ ⋅ ( δ + ( H ) + ε 1 n ) = ∣ V ( H ) ∣ δ + ( H ) + ( ∣ V h i g h ∣ − c ∣ V l o w ∣ ) ⋅ ε 1 n ≤ ∣ V ( H ) ∣ δ + ( H ) + ( ∣ V ( H ) ∣ − ( c + 1 ) ∣ V l o w ∣ ) ⋅ ε 1 n . \begin{aligned}
|V(H)|\delta^+(H)
&\le\sum_{v\in V(H)}d^+(v)
=\sum_{v\in V(H)}d^-(v)
=\sum_{v\in V_{\mathrm{low}}}d^-(v)+\sum_{v\in V_{\mathrm{high}}}d^-(v)\\
&\le|V_{\mathrm{low}}|\cdot(\delta^+(H)-c\varepsilon_1n)+|V_{\mathrm{high}}|\cdot\Delta^-(H)\\
&\le|V_{\mathrm{low}}|\cdot(\delta^+(H)-c\varepsilon_1n)+|V_{\mathrm{high}}|\cdot(\delta^+(H)+\varepsilon_1n)\\
&=|V(H)|\delta^+(H)+(|V_{\mathrm{high}}|-c|V_{\mathrm{low}}|)\cdot\varepsilon_1n\\
&\le|V(H)|\delta^+(H)+(|V(H)|-(c+1)|V_{\mathrm{low}}|)\cdot\varepsilon_1n.
\end{aligned} ∣ V ( H ) ∣ δ + ( H ) ≤ v ∈ V ( H ) ∑ d + ( v ) = v ∈ V ( H ) ∑ d − ( v ) = v ∈ V low ∑ d − ( v ) + v ∈ V high ∑ d − ( v ) ≤ ∣ V low ∣ ⋅ ( δ + ( H ) − c ε 1 n ) + ∣ V high ∣ ⋅ Δ − ( H ) ≤ ∣ V low ∣ ⋅ ( δ + ( H ) − c ε 1 n ) + ∣ V high ∣ ⋅ ( δ + ( H ) + ε 1 n ) = ∣ V ( H ) ∣ δ + ( H ) + ( ∣ V high ∣ − c ∣ V low ∣ ) ⋅ ε 1 n ≤ ∣ V ( H ) ∣ δ + ( H ) + ( ∣ V ( H ) ∣ − ( c + 1 ) ∣ V low ∣ ) ⋅ ε 1 n .
This implies that
∣ V l o w ∣ ≤ ∣ V ( H ) ∣ c + 1 ≤ n ε 1 . |V_{\mathrm{low}}| \le\frac{|V(H)|}{c+1} \le n\sqrt{\varepsilon_1}. ∣ V low ∣ ≤ c + 1 ∣ V ( H ) ∣ ≤ n ε 1 .
We can finally bound the minimum semidegree of H [ V ′ ∖ V l o w ] H[V' \setminus V_{\mathrm{low}}] H [ V ′ ∖ V low ] using the above bound on the size of V l o w V_{\mathrm{low}} V low and ∣ V ( H ) ∖ V ′ ∣ ≤ n − k ⋅ δ + ( H ) ≤ n ε 1 |V(H) \setminus V'| \le n-k\cdot\delta^+(H) \le n\varepsilon_1 ∣ V ( H ) ∖ V ′ ∣ ≤ n − k ⋅ δ + ( H ) ≤ n ε 1 :
δ + ( H [ V ′ ∖ V l o w ] ) ≥ δ + ( H ) − ∣ V ( H ) ∖ V ′ ∣ − ∣ V l o w ∣ ≥ δ + ( H ) − n ε 1 − n ε 1 ≥ δ + ( H ) − n ε 1 − n ε 1 ≥ n k ( 1 − ε 1 ) − n ε 2 k ≥ n k ( 1 − ε ) \begin{aligned}
\delta^+(H[V' \setminus V_{\mathrm{low}}]) \ge\delta^+(H)-|V(H)\setminus V'|-|V_{\mathrm{low}}| \ge\delta^+(H)-n\varepsilon_1-n\sqrt{\varepsilon_1} \\
&\ge\delta^+(H)-n\sqrt{\varepsilon_1}-n\sqrt{\varepsilon_1} \ge\frac{n}{k}(1-\varepsilon_1)-\frac{n\varepsilon}{2k} \ge\frac{n}{k}(1-\varepsilon)
\end{aligned} δ + ( H [ V ′ ∖ V low ]) ≥ δ + ( H ) − ∣ V ( H ) ∖ V ′ ∣ − ∣ V low ∣ ≥ δ + ( H ) − n ε 1 − n ε 1 ≥ δ + ( H ) − n ε 1 − n ε 1 ≥ k n ( 1 − ε 1 ) − 2 k n ε ≥ k n ( 1 − ε )
and
δ − ( H [ V ′ ∖ V l o w ] ) ≥ ( δ + ( H ) − c ε 1 n ) − ∣ V ( H ) ∖ V ′ ∣ − ∣ V l o w ∣ ≥ δ + ( H ) − c ε 1 n − n ε 1 − n ε 1 = δ + ( H ) − n ε 1 − n ε 1 ≥ n k ( 1 − ε 1 ) − n ε 2 k ≥ n k ( 1 − ε ) . \begin{aligned}
\delta^-(H[V' \setminus V_{\mathrm{low}}]) \ge(\delta^+(H)-c\varepsilon_1n)-|V(H)\setminus V'|-|V_{\mathrm{low}}| \ge\delta^+(H)-c\varepsilon_1n-n\varepsilon_1-n\sqrt{\varepsilon_1} \\
&= \delta^+(H)-n\sqrt{\varepsilon_1}-n\sqrt{\varepsilon_1} \ge\frac{n}{k}(1-\varepsilon_1)-\frac{n\varepsilon}{2k} \ge\frac{n}{k}(1-\varepsilon).
\end{aligned} δ − ( H [ V ′ ∖ V low ]) ≥ ( δ + ( H ) − c ε 1 n ) − ∣ V ( H ) ∖ V ′ ∣ − ∣ V low ∣ ≥ δ + ( H ) − c ε 1 n − n ε 1 − n ε 1 = δ + ( H ) − n ε 1 − n ε 1 ≥ k n ( 1 − ε 1 ) − 2 k n ε ≥ k n ( 1 − ε ) .
Therefore, removing V l o w V_{\mathrm{low}} V low meets the requirement of the claim. □ \square □
This concludes the proof of Lemma 4.2. □ \square □
Approximate structure in the odd case
When ℓ \ell ℓ is odd, the number k k k from Theorem 1.4 is equal to 4. This leads to the following stability lemma, analogous to Lemma 4.2.
Lemma 4.6. Let ℓ > 90 \ell>90 ℓ > 90 be an odd integer divisible by 3. Every C ⃗ ℓ \vec C_\ell C ℓ -free oriented graph G G G on n n n vertices satisfying δ + ( G ) > n 4 \delta^+(G)>\frac{n}{4} δ + ( G ) > 4 n contains a subgraph H H H homomorphic to C ⃗ 4 \vec C_4 C 4 with δ ± ( H ) ≥ n 4 − o ( n ) \delta^{\pm}(H)\ge\frac{n}{4}-o(n) δ ± ( H ) ≥ 4 n − o ( n ) .
Applying Proposition 2.5 to the graph G G G , we obtain a W ⃗ ℓ \vec W_\ell W ℓ -free subgraph H H H with δ + ( H ) ≥ n 4 − o ( n ) \delta^+(H)\ge\frac{n}{4}-o(n) δ + ( H ) ≥ 4 n − o ( n ) . However, in this case, H H H does not necessarily contain a large induced subgraph homomorphic to C ⃗ 4 \vec C_4 C 4 itself. Indeed, a random orientation of a sufficiently large balanced complete bipartite graph contains no odd cycles, has minimum outdegree n 4 − o ( n ) \frac{n}{4}-o(n) 4 n − o ( n ) and does not contain an induced subgraph on n − o ( n ) n-o(n) n − o ( n ) vertices homomorphic to C ⃗ 4 \vec C_4 C 4 . This is why we need to prove the following weaker result first.
Lemma 4.7. Let ℓ > 90 \ell>90 ℓ > 90 be an odd integer divisible by 3. Every W ⃗ ℓ \vec W_\ell W ℓ -free oriented graph H H H on n n n vertices with δ + ( H ) ≥ n 4 − o ( n ) \delta^+(H)\ge\frac{n}{4}-o(n) δ + ( H ) ≥ 4 n − o ( n ) contains an induced bipartite subgraph on n − o ( n ) n-o(n) n − o ( n ) vertices with minimum semidegree at least n 4 − o ( n ) \frac{n}{4}-o(n) 4 n − o ( n ) .
Proof. We start with a claim similar to Claim 4.3.
Claim 4.8. There exists a vertex v 0 ∈ V ( H ) v_0\in V(H) v 0 ∈ V ( H ) such that for every v ∈ V ( H ) v\in V(H) v ∈ V ( H ) , there is a directed path of length at most 6 from v v v to v 0 v_0 v 0 .
Proof. Since H H H is W ⃗ ℓ \vec W_\ell W ℓ -free and ℓ \ell ℓ is divisible by 3, H H H is C ⃗ 3 \vec C_3 C 3 -free. Take any v ∈ V ( H ) v\in V(H) v ∈ V ( H ) and denote X 1 = N + ( v ) X_1=N^+(v) X 1 = N + ( v ) , X i + 1 = N + ( X i ) ∪ X i X_{i+1}=N^+(X_i)\cup X_i X i + 1 = N + ( X i ) ∪ X i for i = 1 , 2 i=1,2 i = 1 , 2 . Since for any i i i , H [ X i ] H[X_i] H [ X i ] is C ⃗ 3 \vec C_3 C 3 -free, there must exist a vertex u ∈ X i u\in X_i u ∈ X i such that ∣ N + ( u ) ∩ X i ∣ < 0.3465 ⋅ ∣ X i ∣ |N^+(u)\cap X_i|<0.3465\cdot|X_i| ∣ N + ( u ) ∩ X i ∣ < 0.3465 ⋅ ∣ X i ∣ (Lemma 4.1 applied with m = 1 m=1 m = 1 ). Hence,
∣ X i + 1 ∣ − ∣ X i ∣ > δ + ( H ) − 0.3465 ⋅ ∣ X i ∣ = n 4 − o ( n ) − 0.3465 ⋅ ∣ X i ∣ . |X_{i+1}|-|X_i|>\delta^+(H)-0.3465\cdot|X_i|=\frac{n}{4}-o(n)-0.3465\cdot|X_i|. ∣ X i + 1 ∣ − ∣ X i ∣ > δ + ( H ) − 0.3465 ⋅ ∣ X i ∣ = 4 n − o ( n ) − 0.3465 ⋅ ∣ X i ∣.
This in particular implies that ∣ X 3 ∣ > 0.52 n − o ( n ) |X_3|>0.52n-o(n) ∣ X 3 ∣ > 0.52 n − o ( n ) . In other words, every vertex v v v has a directed path of length at most 3 to over a half of V ( H ) V(H) V ( H ) . Therefore there must exist a vertex v 0 v_0 v 0 to which there is a directed path of length at most 3 from over a half of V ( H ) V(H) V ( H ) . Concatenating two such paths through a common vertex, we obtain a directed walk, and hence also a directed path, of length at most 6 from any v v v to v 0 v_0 v 0 .
Take the vertex v 0 ∈ V ( H ) v_0 \in V(H) v 0 ∈ V ( H ) from Claim 4.8 and define
V 1 : = N + ( v 0 ) , V_1 := N^{+}(v_0), V 1 := N + ( v 0 ) ,
V i : = N + ( V i − 1 ) ∖ ( ⋃ j < i V j ) for i = 2 , 3 , 4. V_i := N^{+}(V_{i-1}) \setminus\left(\bigcup_{j<i} V_j\right) \quad\text{for } i=2,3,4. V i := N + ( V i − 1 ) ∖ ( j < i ⋃ V j ) for i = 2 , 3 , 4.
In other words, for i ≤ 3 i \le3 i ≤ 3 , V i V_i V i is the set of vertices at distance exactly i i i from v 0 v_0 v 0 , while V 4 V_4 V 4 consists of the vertices at distance exactly 4 and possibly of v 0 v_0 v 0 itself. We now observe that the following holds.
Claim 4.9. For any i ≡ j ( m o d 2 ) i \equiv j \pmod{2} i ≡ j ( mod 2 ) , there are no arcs from V i V_i V i to V j V_j V j .
Proof. Assume there is an arc x y xy x y with x ∈ V i x \in V_i x ∈ V i , y ∈ V j y \in V_j y ∈ V j , i − j ∈ { − 2 , 0 , 2 } i-j \in\{-2,0,2\} i − j ∈ { − 2 , 0 , 2 } . Then there are directed paths of lengths i + 1 i+1 i + 1 and j j j from v 0 v_0 v 0 to y y y . We also know there is a directed path of length d ≤ 6 d \le6 d ≤ 6 from y y y to v 0 v_0 v 0 , which together with the previously mentioned paths forms intersecting closed directed walks of lengths d + i + 1 d+i+1 d + i + 1 and d + j d+j d + j . Now, since
( d + i + 1 ) − ( d + j ) = i − j + 1 ∈ { − 1 , 1 , 3 } , (d+i+1)-(d+j)=i-j+1 \in\{-1,1,3\}, ( d + i + 1 ) − ( d + j ) = i − j + 1 ∈ { − 1 , 1 , 3 } ,
the number gcd ( d + i + 1 , d + j ) \gcd(d+i+1,d+j) g cd( d + i + 1 , d + j ) divides 3, and hence it divides ℓ \ell ℓ as well. Moreover, ℓ > 90 ≥ ( d + i ) ( d + j − 1 ) \ell> 90 \ge(d+i)(d+j-1) ℓ > 90 ≥ ( d + i ) ( d + j − 1 ) , therefore, according to Corollary 2.2 , the closed directed walks of lengths d + i + 1 d+i+1 d + i + 1 and d + j d+j d + j can be composed into a closed directed walk of length ℓ \ell ℓ , contradicting our assumptions on H H H .
With careful analysis it is possible to reduce the bound to ℓ > 39 \ell> 39 ℓ > 39 . Key observation is that there is also a cycle of length at most 6 containing v 0 v_0 v 0 . For the sake of brevity we omit the proof.
Claim 4.9 implies that the subgraph of H H H induced by V ′ : = V 1 ∪ V 2 ∪ V 3 ∪ V 4 V' := V_1 \cup V_2 \cup V_3 \cup V_4 V ′ := V 1 ∪ V 2 ∪ V 3 ∪ V 4 is bipartite with parts V 1 ∪ V 3 V_1 \cup V_3 V 1 ∪ V 3 and V 2 ∪ V 4 V_2 \cup V_4 V 2 ∪ V 4 . We now prove that ∣ V ′ ∣ ≥ n − o ( n ) |V'| \ge n-o(n) ∣ V ′ ∣ ≥ n − o ( n ) . Denote T : = V ( H ) ∖ V ′ T := V(H) \setminus V' T := V ( H ) ∖ V ′ .
Claim 4.10. For any ε ≥ 0 \varepsilon\ge0 ε ≥ 0 there exists ε 1 > 0 \varepsilon_1 > 0 ε 1 > 0 such that δ + ( H ) ≥ n 4 ( 1 − ε 1 ) \delta^{+}(H) \ge\frac{n}{4}(1-\varepsilon_1) δ + ( H ) ≥ 4 n ( 1 − ε 1 ) implies ∣ T ∣ ≤ ε n |T| \le\varepsilon n ∣ T ∣ ≤ ε n . In particular, ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) .
Proof. Take ε 1 < 3 ε 2 1 + 3 ε \varepsilon_1 < \frac{3\varepsilon^2}{1+3\varepsilon} ε 1 < 1 + 3 ε 3 ε 2 and assume that δ + ( H ) ≥ n 4 ( 1 − ε 1 ) \delta^{+}(H) \ge\frac{n}{4}(1-\varepsilon_1) δ + ( H ) ≥ 4 n ( 1 − ε 1 ) . First bound the number of arcs leaving V ′ V' V ′ as below.
δ + ( H ) ⋅ ( n − ∣ T ∣ ) ≤ ∑ v ∈ V ′ d + ( v ) = e ( V ′ , V ′ ) + e ( V ′ , T ) ≤ ( n − ∣ T ∣ ) 2 4 + ∣ V 4 ∣ ∣ T ∣ . \delta^{+}(H)\cdot(n-|T|) \le\sum_{v\in V'}d^{+}(v)=e(V',V')+e(V',T)\le\frac{(n-|T|)^2}{4}+|V_4||T|. δ + ( H ) ⋅ ( n − ∣ T ∣ ) ≤ v ∈ V ′ ∑ d + ( v ) = e ( V ′ , V ′ ) + e ( V ′ , T ) ≤ 4 ( n − ∣ T ∣ ) 2 + ∣ V 4 ∣∣ T ∣.
The last inequality is due to H [ V ′ ] H[V'] H [ V ′ ] being bipartite and arcs leaving V ′ V' V ′ solely from V 4 V_4 V 4 , as a vertex with an inneighbor in V i V_i V i for some i ≤ 3 i \le3 i ≤ 3 is at distance at most 4 from v 0 v_0 v 0 and thus belongs to V ′ V' V ′ . This can be rewritten as
n 4 ( 1 − ε 1 ) ≤ δ + ( H ) ≤ n − ∣ T ∣ 4 + ∣ V 4 ∣ ⋅ ∣ T ∣ n − ∣ T ∣ . \frac{n}{4}(1-\varepsilon_1)\le\delta^{+}(H)\le\frac{n-|T|}{4}+|V_4|\cdot\frac{|T|}{n-|T|}. 4 n ( 1 − ε 1 ) ≤ δ + ( H ) ≤ 4 n − ∣ T ∣ + ∣ V 4 ∣ ⋅ n − ∣ T ∣ ∣ T ∣ .
Assume now that ∣ T ∣ > ε n |T| > \varepsilon n ∣ T ∣ > ε n , aiming for a contradiction. We bound ∣ V 4 ∣ |V_4| ∣ V 4 ∣ using the inequality above:
∣ V 4 ∣ ≥ ∣ T ∣ − ε 1 n 4 ⋅ n − ∣ T ∣ ∣ T ∣ = n − ∣ T ∣ 4 − n − ∣ T ∣ 4 ∣ T ∣ ⋅ ε 1 n > n − ∣ T ∣ 4 − ε 1 4 ε n = 1 4 ( ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ + ∣ V 4 ∣ ) − ε 1 4 ε n , \begin{aligned}
|V_4| \ge\frac{|T|-\varepsilon_1 n}{4}\cdot\frac{n-|T|}{|T|}=\frac{n-|T|}{4}-\frac{n-|T|}{4|T|}\cdot\varepsilon_1 n>\frac{n-|T|}{4}-\frac{\varepsilon_1}{4\varepsilon}n \\
&=\frac{1}{4}(|V_1|+|V_2|+|V_3|+|V_4|)-\frac{\varepsilon_1}{4\varepsilon}n,
\end{aligned} ∣ V 4 ∣ ≥ 4 ∣ T ∣ − ε 1 n ⋅ ∣ T ∣ n − ∣ T ∣ = 4 n − ∣ T ∣ − 4∣ T ∣ n − ∣ T ∣ ⋅ ε 1 n > 4 n − ∣ T ∣ − 4 ε ε 1 n = 4 1 ( ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ + ∣ V 4 ∣ ) − 4 ε ε 1 n ,
which implies that
∣ V 4 ∣ > 1 3 ( ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ ) − ε 1 3 ε n . |V_4|>\frac{1}{3}(|V_1|+|V_2|+|V_3|)-\frac{\varepsilon_1}{3\varepsilon}n. ∣ V 4 ∣ > 3 1 ( ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ ) − 3 ε ε 1 n .
We now focus on bounding ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ |V_1|+|V_2|+|V_3| ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ . Notice that all arcs from V 1 V_1 V 1 leave to V 2 V_2 V 2 and all arcs from V 2 V_2 V 2 leave either back to V 1 V_1 V 1 or to V 3 V_3 V 3 . Moreover, as H H H is an oriented graph, between a vertex of V 1 V_1 V 1 and a vertex of V 2 V_2 V 2 there is at most one arc, hence
δ + ( H ) ⋅ ( ∣ V 1 ∣ + ∣ V 2 ∣ ) ≤ e ( V 1 , V 2 ) + e ( V 2 , V 1 ∪ V 3 ) ≤ ∣ V 1 ∣ ∣ V 2 ∣ + ∣ V 2 ∣ ∣ V 3 ∣ = ∣ V 2 ∣ ( ∣ V 1 ∣ + ∣ V 3 ∣ ) \delta^+(H)\cdot(|V_1|+|V_2|)\le e(V_1,V_2)+e(V_2,V_1\cup V_3)\le|V_1||V_2|+|V_2||V_3|=|V_2|(|V_1|+|V_3|) δ + ( H ) ⋅ ( ∣ V 1 ∣ + ∣ V 2 ∣ ) ≤ e ( V 1 , V 2 ) + e ( V 2 , V 1 ∪ V 3 ) ≤ ∣ V 1 ∣∣ V 2 ∣ + ∣ V 2 ∣∣ V 3 ∣ = ∣ V 2 ∣ ( ∣ V 1 ∣ + ∣ V 3 ∣ )
and therefore, using ∣ V 1 ∣ ≥ δ + ( H ) |V_1|\ge\delta^+(H) ∣ V 1 ∣ ≥ δ + ( H ) ,
∣ V 1 ∣ + ∣ V 3 ∣ ≥ δ + ( H ) ⋅ ∣ V 1 ∣ ∣ V 2 ∣ + δ + ( H ) ≥ ( δ + ( H ) ) 2 ∣ V 2 ∣ + δ + ( H ) . |V_1|+|V_3|\ge\delta^+(H)\cdot\frac{|V_1|}{|V_2|}+\delta^+(H)\ge\frac{(\delta^+(H))^2}{|V_2|}+\delta^+(H). ∣ V 1 ∣ + ∣ V 3 ∣ ≥ δ + ( H ) ⋅ ∣ V 2 ∣ ∣ V 1 ∣ + δ + ( H ) ≥ ∣ V 2 ∣ ( δ + ( H ) ) 2 + δ + ( H ) .
Thus, by the inequality of arithmetic and geometric means,
∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ ≥ ( δ + ( H ) ) 2 ∣ V 2 ∣ + δ + ( H ) + ∣ V 2 ∣ ≥ 3 δ + ( H ) |V_1|+|V_2|+|V_3|\ge\frac{(\delta^+(H))^2}{|V_2|}+\delta^+(H)+|V_2|\ge3\delta^+(H) ∣ V 1 ∣ + ∣ V 2 ∣ + ∣ V 3 ∣ ≥ ∣ V 2 ∣ ( δ + ( H ) ) 2 + δ + ( H ) + ∣ V 2 ∣ ≥ 3 δ + ( H )
and
∣ V ′ ∣ > 4 δ + ( H ) − ε 1 3 ε n > 4 ⋅ n 4 ( 1 − ε 1 ) − ε 1 3 ε n = n ( 1 − ε 1 ⋅ 3 ε + 1 3 ε ) > n ( 1 − ε ) . |V'|>4\delta^+(H)-\frac{\varepsilon_1}{3\varepsilon}n>4\cdot\frac{n}{4}(1-\varepsilon_1)-\frac{\varepsilon_1}{3\varepsilon}n=n\left(1-\varepsilon_1\cdot\frac{3\varepsilon+1}{3\varepsilon}\right)>n(1-\varepsilon). ∣ V ′ ∣ > 4 δ + ( H ) − 3 ε ε 1 n > 4 ⋅ 4 n ( 1 − ε 1 ) − 3 ε ε 1 n = n ( 1 − ε 1 ⋅ 3 ε 3 ε + 1 ) > n ( 1 − ε ) .
This is a contradiction, as by our previous assumptions, ∣ V ′ ∣ = n − ∣ T ∣ ≤ n − ε n |V'|=n-|T|\le n-\varepsilon n ∣ V ′ ∣ = n − ∣ T ∣ ≤ n − ε n .
The graph H [ V ′ ] H[V'] H [ V ′ ] is large and bipartite as wanted, but it does not need to satisfy δ + ( H [ V ′ ] ) ≥ n 4 − o ( n ) \delta^+(H[V'])\ge\frac{n}{4}-o(n) δ + ( H [ V ′ ]) ≥ 4 n − o ( n ) yet. We need to remove some vertices from V ′ V' V ′ .
Claim 4.11. Let ε > 0 \varepsilon>0 ε > 0 . There exists ε 1 > 0 \varepsilon_1>0 ε 1 > 0 such that if δ + ( H ) ≥ n 4 ( 1 − ε 1 ) \delta^+(H)\ge\frac{n}{4}(1-\varepsilon_1) δ + ( H ) ≥ 4 n ( 1 − ε 1 ) , then one can remove at most ε n \varepsilon n ε n vertices from V ′ V' V ′ so that the subgraph of H H H induced by the remaining vertices has minimum semidegree at least n 4 − 3 ε n \frac{n}{4}-3\varepsilon n 4 n − 3 ε n . In other words, one can remove o ( n ) o(n) o ( n ) vertices from V ′ V' V ′ so that the obtained induced subgraph has minimum semidegree at least n 4 − o ( n ) \frac{n}{4}-o(n) 4 n − o ( n ) .
Proof. Denote n ′ : = ∣ V ′ ∣ = n − ∣ T ∣ n':=|V'|=n-|T| n ′ := ∣ V ′ ∣ = n − ∣ T ∣ . By Claim 4.10, there exists ε 2 > 0 \varepsilon_2>0 ε 2 > 0 , for which δ + ( H ) ≥ n 4 ( 1 − ε 2 ) \delta^+(H)\ge\frac{n}{4}(1-\varepsilon_2) δ + ( H ) ≥ 4 n ( 1 − ε 2 ) implies that ∣ T ∣ ≤ ε 2 8 n |T|\le\frac{\varepsilon^2}{8}n ∣ T ∣ ≤ 8 ε 2 n , so n ′ ≥ n − ε 2 8 n n'\ge n-\frac{\varepsilon^2}{8}n n ′ ≥ n − 8 ε 2 n .
Take ε 1 : = min ( ε 2 , ε 2 2 ) \varepsilon_1:=\min(\varepsilon_2,\frac{\varepsilon^2}{2}) ε 1 := min ( ε 2 , 2 ε 2 ) . Then δ + ( H ) ≥ n 4 ( 1 − ε 1 ) \delta^+(H)\ge\frac{n}{4}(1-\varepsilon_1) δ + ( H ) ≥ 4 n ( 1 − ε 1 ) implies
n ′ ≥ n − ε 2 8 n ≥ n ( 1 − ε ) , n'\ge n-\frac{\varepsilon^2}{8}n\ge n(1-\varepsilon), n ′ ≥ n − 8 ε 2 n ≥ n ( 1 − ε ) , δ + ( H [ V ′ ] ) ≥ n 4 ( 1 − ε 1 ) − ∣ T ∣ ≥ n 4 ( 1 − ε 2 ) ≥ n ′ 4 ( 1 − ε 2 ) . \delta^+(H[V'])\ge\frac{n}{4}(1-\varepsilon_1)-|T|\ge\frac{n}{4}(1-\varepsilon^2)\ge\frac{n'}{4}(1-\varepsilon^2). δ + ( H [ V ′ ]) ≥ 4 n ( 1 − ε 1 ) − ∣ T ∣ ≥ 4 n ( 1 − ε 2 ) ≥ 4 n ′ ( 1 − ε 2 ) .
Consider now a set Y Y Y of y = ε n ′ y=\varepsilon n' y = ε n ′ vertices of the smallest indegree in H [ V ′ ] H[V'] H [ V ′ ] . Denote s : = max v ∈ Y { d H [ V ′ ] − ( v ) } s:=\max_{v\in Y}\{d^-_{H[V']}(v)\} s := max v ∈ Y { d H [ V ′ ] − ( v )} . Then δ − ( H [ V ′ ∖ Y ] ) ≥ s − y \delta^-(H[V'\setminus Y])\ge s-y δ − ( H [ V ′ ∖ Y ]) ≥ s − y . Calculating the number of arcs of H [ V ′ ] H[V'] H [ V ′ ] from V ′ ∖ Y V'\setminus Y V ′ ∖ Y we obtain the following.
( n ′ − y ) n ′ 4 ( 1 − ε 2 ) ≤ ∑ v ∈ V ′ ∖ Y d H [ V ′ ] + ( v ) = e ( V ′ ∖ Y , V ′ ∖ Y ) + e ( V ′ ∖ Y , Y ) ≤ ( n ′ − y ) 2 4 + y s . (n'-y)\frac{n'}{4}(1-\varepsilon^2)\le\sum_{v\in V'\setminus Y}d^+_{H[V']}(v)=e(V'\setminus Y,V'\setminus Y)+e(V'\setminus Y,Y)
\le\frac{(n'-y)^2}{4}+ys. ( n ′ − y ) 4 n ′ ( 1 − ε 2 ) ≤ v ∈ V ′ ∖ Y ∑ d H [ V ′ ] + ( v ) = e ( V ′ ∖ Y , V ′ ∖ Y ) + e ( V ′ ∖ Y , Y ) ≤ 4 ( n ′ − y ) 2 + y s .
Here the first inequality follows from the bound on δ + ( H [ V ′ ] ) \delta^+(H[V']) δ + ( H [ V ′ ]) above, while the last one is a consequence of the bipartiteness of H [ V ′ ∖ Y ] H[V'\setminus Y] H [ V ′ ∖ Y ] together with the definition of s s s . This allows us to lower-bound s s s .
s ≥ ( n ′ − y ) ( y − ε 2 n ′ ) 4 y = ( n ′ − ε n ′ ) ( ε n ′ − ε 2 n ′ ) 4 ε n ′ = n ′ ( 1 − ε ) 2 4 > n ′ 4 ( 1 − 2 ε ) . s\ge\frac{(n'-y)(y-\varepsilon^2n')}{4y}=\frac{(n'-\varepsilon n')(\varepsilon n'-\varepsilon^2n')}{4\varepsilon n'}=\frac{n'(1-\varepsilon)^2}{4}>\frac{n'}{4}(1-2\varepsilon). s ≥ 4 y ( n ′ − y ) ( y − ε 2 n ′ ) = 4 ε n ′ ( n ′ − ε n ′ ) ( ε n ′ − ε 2 n ′ ) = 4 n ′ ( 1 − ε ) 2 > 4 n ′ ( 1 − 2 ε ) .
This means that δ − ( H [ V ′ ∖ Y ] ) ≥ s − y > n ′ 4 − 2 ε n ′ \delta^-(H[V'\setminus Y])\ge s-y>\frac{n'}{4}-2\varepsilon n' δ − ( H [ V ′ ∖ Y ]) ≥ s − y > 4 n ′ − 2 ε n ′ . Clearly, after removing ε n ′ \varepsilon n' ε n ′ vertices, δ + ( H [ V ′ ∖ Y ] ) ≥ δ + ( H [ V ′ ] ) − ε n ′ > n ′ 4 − 2 ε n ′ \delta^+(H[V'\setminus Y])\ge\delta^+(H[V'])-\varepsilon n'>\frac{n'}{4}-2\varepsilon n' δ + ( H [ V ′ ∖ Y ]) ≥ δ + ( H [ V ′ ]) − ε n ′ > 4 n ′ − 2 ε n ′ , therefore
δ ± ( H [ V ′ ∖ Y ] ) ≥ n ′ ( 1 4 − 2 ε ) ≥ n ( 1 − ε ) ( 1 4 − 2 ε ) ≥ n 4 − 3 ε n \delta^\pm(H[V'\setminus Y])\ge n'\left(\frac{1}{4}-2\varepsilon\right)\ge n(1-\varepsilon)\left(\frac{1}{4}-2\varepsilon\right)\ge\frac{n}{4}-3\varepsilon n δ ± ( H [ V ′ ∖ Y ]) ≥ n ′ ( 4 1 − 2 ε ) ≥ n ( 1 − ε ) ( 4 1 − 2 ε ) ≥ 4 n − 3 ε n
as needed.
By Claim 4.11, after removing set Y Y Y of vertices from V ′ V' V ′ , the graph H [ V ′ ∖ Y ] H[V'\setminus Y] H [ V ′ ∖ Y ] satisfies the conditions of Lemma 4.7 .
Before we proceed to the proof of Lemma 4.6 , we make a general observation that will be useful later.
Observation 4.12. Let G G G be an oriented graph on n n n vertices with δ + ( G ) > n 4 \delta^+(G)>\frac{n}{4} δ + ( G ) > 4 n , and let V ( G ) = L ∪ R ∪ T V(G)=L\cup R\cup T V ( G ) = L ∪ R ∪ T be a partition with ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) . For n n n large enough, there exists a directed path P P P in G G G of length at most 3 with endpoints u , v u,v u , v in L ∪ R L\cup R L ∪ R and all internal vertices in T T T , such that the length of P P P is odd if u u u and v v v lie in the same part of the partition ( L , R ) (L,R) ( L , R ) and even otherwise.
Proof. Assume that no such path exists. Then, there are no arcs inside L L L or R R R , because any such arc would be a wanted path satisfying all the requirements. Partition T T T into T L ∪ T R ∪ T 0 T_L\cup T_R\cup T_0 T L ∪ T R ∪ T 0 , where
T L = { t ∈ T : N − ( t ) ∩ R ≠ ∅ } , T R = { t ∈ T : N − ( t ) ∩ L ≠ ∅ } , T 0 = T ∖ ( T L ∪ T R ) . T_L=\{t\in T:N^-(t)\cap R\ne\varnothing\},
\qquad
T_R=\{t\in T:N^-(t)\cap L\ne\varnothing\},
\qquad
T_0=T\setminus(T_L\cup T_R). T L = { t ∈ T : N − ( t ) ∩ R = ∅ } , T R = { t ∈ T : N − ( t ) ∩ L = ∅ } , T 0 = T ∖ ( T L ∪ T R ) .
Notice that T L T_L T L and T R T_R T R are disjoint, because a vertex t t t lying in both would have inneighbors in both L L L and R R R and, by the outdegree assumption, an outneighbor in L ∪ R L\cup R L ∪ R , creating a wanted path of length 2. For the same reason, for every t ∈ T L t\in T_L t ∈ T L , we have N + ( t ) ∩ L = ∅ N^+(t)\cap L=\varnothing N + ( t ) ∩ L = ∅ , so ∣ N + ( t ) ∩ R ∣ ≥ n 4 − o ( n ) |N^+(t)\cap R|\ge\frac{n}{4}-o(n) ∣ N + ( t ) ∩ R ∣ ≥ 4 n − o ( n ) . Consequently, there are no arcs in T L T_L T L , because an arc t t ′ tt' t t ′ inside T L T_L T L , together with u ∈ N − ( t ) ∩ R u\in N^-(t)\cap R u ∈ N − ( t ) ∩ R and v ∈ N + ( t ′ ) ∩ R v\in N^+(t')\cap R v ∈ N + ( t ′ ) ∩ R , would give a path u t t ′ v utt'v u t t ′ v of length 3 with both endpoints in R R R . Symmetrically for T R T_R T R . Consider the partition of V ( G ) ∖ T 0 V(G) \setminus T_0 V ( G ) ∖ T 0 into L ∪ T L L \cup T_L L ∪ T L and R ∪ T R R \cup T_R R ∪ T R . By the above, every arc of G − T 0 G-T_0 G − T 0 joins the two parts. Moreover no arc leads from L ∪ R L \cup R L ∪ R to T 0 T_0 T 0 , so at most ∣ T ∣ ∣ T 0 ∣ |T||T_0| ∣ T ∣∣ T 0 ∣ arcs leave G − T 0 G-T_0 G − T 0 . Hence, by summing the outdegrees of the vertices of G − T 0 G-T_0 G − T 0 we obtain,
n 4 ( n − ∣ T 0 ∣ ) ≤ ∑ v ∈ V ( G ) ∖ T 0 d + ( v ) ≤ e ( G − T 0 ) + ∣ T ∣ ∣ T 0 ∣ ≤ ( n − ∣ T 0 ∣ ) 2 4 + ∣ T ∣ ∣ T 0 ∣ . \frac{n}{4}(n-|T_0|) \le\sum_{v\in V(G)\setminus T_0} d^{+}(v) \le e(G-T_0)+|T||T_0| \le\frac{(n-|T_0|)^2}{4}+|T||T_0|. 4 n ( n − ∣ T 0 ∣ ) ≤ v ∈ V ( G ) ∖ T 0 ∑ d + ( v ) ≤ e ( G − T 0 ) + ∣ T ∣∣ T 0 ∣ ≤ 4 ( n − ∣ T 0 ∣ ) 2 + ∣ T ∣∣ T 0 ∣.
This leads to 1 4 ∣ T 0 ∣ ( n − ∣ T 0 ∣ − 4 ∣ T ∣ ) < 0 \frac{1}{4}|T_0|(n-|T_0|-4|T|)<0 4 1 ∣ T 0 ∣ ( n − ∣ T 0 ∣ − 4∣ T ∣ ) < 0 , which is false for large n n n , as ∣ T 0 ∣ ≤ ∣ T ∣ = o ( n ) |T_0|\le|T|=o(n) ∣ T 0 ∣ ≤ ∣ T ∣ = o ( n ) . □
Proof of Lemma 4.6. Take the graph G G G and use Proposition 2.5 and Lemma 4.7 to obtain a bipartite subgraph H H H with δ ± ( H ) ≥ n 4 − o ( n ) \delta^{\pm}(H)\ge\frac{n}{4}-o(n) δ ± ( H ) ≥ 4 n − o ( n ) . This allows us to partition V ( G ) V(G) V ( G ) into L L L , R R R (the parts of H H H ), and the remaining vertex set T T T (short for ‘trash’). Moreover, ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) . Note there may be extra arcs in G [ L ∪ R ] G[L\cup R] G [ L ∪ R ] which violate the bipartition ( L , R ) (L,R) ( L , R ) .
The path P P P from Observation 4.12, applied to the partition ( L , R , T ) (L,R,T) ( L , R , T ) , will serve as our anchor. Assume without loss of generality that u ∈ L u\in L u ∈ L . Greedily extend P P P beyond v v v inside H H H , avoiding the vertices chosen before (the condition δ ± ( H ) ≥ n 4 − o ( n ) \delta^{\pm}(H)\ge\frac{n}{4}-o(n) δ ± ( H ) ≥ 4 n − o ( n ) guarantees this is always possible), to obtain a directed path Q Q Q of length ℓ − 3 \ell-3 ℓ − 3 from u u u to some vertex w w w . Every arc of H H H joins L L L with R R R , so the part containing w w w is obtained from the part containing v v v by ℓ − 3 − ∣ P ∣ \ell-3-|P| ℓ − 3 − ∣ P ∣ swaps, while by the choice of P P P the part containing v v v is obtained from the one containing u u u by ∣ P ∣ − 1 |P|-1 ∣ P ∣ − 1 swaps. Altogether w w w lies in the part obtained from L L L by ℓ − 4 \ell-4 ℓ − 4 swaps, that is, w ∈ R w\in R w ∈ R . Denote
V 1 = N H + ( w ) ∖ Q , V 4 = N H − ( u ) ∖ Q . V_1=N_H^{+}(w)\setminus Q,\qquad V_4=N_H^{-}(u)\setminus Q. V 1 = N H + ( w ) ∖ Q , V 4 = N H − ( u ) ∖ Q .
Note that V 1 ⊆ L V_1\subseteq L V 1 ⊆ L and V 4 ⊆ R V_4\subseteq R V 4 ⊆ R . Since δ ± ( H ) ≥ n 4 − o ( n ) \delta^{\pm}(H)\ge\frac{n}{4}-o(n) δ ± ( H ) ≥ 4 n − o ( n ) , ∣ V 1 ∣ ≥ n 4 − o ( n ) |V_1|\ge\frac{n}{4}-o(n) ∣ V 1 ∣ ≥ 4 n − o ( n ) and ∣ V 4 ∣ ≥ n 4 − o ( n ) |V_4|\ge\frac{n}{4}-o(n) ∣ V 4 ∣ ≥ 4 n − o ( n ) . Observe moreover that there are no arcs from V 1 V_1 V 1 to V 4 V_4 V 4 in G G G , as such an arc would close the path Q Q Q into a C ℓ → \overrightarrow{C_\ell} C ℓ . Now let
V 2 = R ∖ V 4 , V 3 = L ∖ V 1 . V_2=R\setminus V_4,\qquad V_3=L\setminus V_1. V 2 = R ∖ V 4 , V 3 = L ∖ V 1 .
Since there are no arcs from V 1 V_1 V 1 to V 4 V_4 V 4 and δ ± ( H ) ≥ n 4 − o ( n ) \delta^{\pm}(H)\ge\frac{n}{4}-o(n) δ ± ( H ) ≥ 4 n − o ( n ) , we infer that V 2 ⊇ N H + ( V 1 ) V_2\supseteq N_H^{+}(V_1) V 2 ⊇ N H + ( V 1 ) has at least n 4 − o ( n ) \frac{n}{4}-o(n) 4 n − o ( n ) vertices and similarly that ∣ V 3 ∣ ≥ n 4 − o ( n ) |V_3|\ge\frac{n}{4}-o(n) ∣ V 3 ∣ ≥ 4 n − o ( n ) . This also implies that for any i i i , ∣ V i ∣ ≤ n 4 + o ( n ) |V_i|\le\frac{n}{4}+o(n) ∣ V i ∣ ≤ 4 n + o ( n ) . In other words, the partition V 1 , V 2 , V 3 , V 4 V_1,V_2,V_3,V_4 V 1 , V 2 , V 3 , V 4 is nearly balanced. Observe that
e ( V 1 , V 2 ) = e ( V 1 , R ) − e ( V 1 , V 4 ) = e ( V 1 , R ) ≥ ∣ V 1 ∣ ⋅ δ + ( H ) ≥ n 2 16 − o ( n 2 ) , e(V_1,V_2)=e(V_1,R)-e(V_1,V_4)=e(V_1,R)\ge|V_1|\cdot\delta^{+}(H)\ge\frac{n^2}{16}-o(n^2), e ( V 1 , V 2 ) = e ( V 1 , R ) − e ( V 1 , V 4 ) = e ( V 1 , R ) ≥ ∣ V 1 ∣ ⋅ δ + ( H ) ≥ 16 n 2 − o ( n 2 ) ,
e ( V 2 , V 1 ) ≤ ∣ V 2 ∣ ∣ V 1 ∣ − e ( V 1 , V 2 ) ≤ ( n 4 + o ( n ) ) 2 − ( n 2 16 − o ( n 2 ) ) ≤ o ( n 2 ) , e(V_2,V_1)\le|V_2||V_1|-e(V_1,V_2)\le\left(\frac{n}{4}+o(n)\right)^2-\left(\frac{n^2}{16}-o(n^2)\right)\le o(n^2), e ( V 2 , V 1 ) ≤ ∣ V 2 ∣∣ V 1 ∣ − e ( V 1 , V 2 ) ≤ ( 4 n + o ( n ) ) 2 − ( 16 n 2 − o ( n 2 ) ) ≤ o ( n 2 ) ,
e ( V 2 , V 3 ) = e ( V 2 , L ) − e ( V 2 , V 1 ) ≥ ∣ V 2 ∣ ⋅ δ + ( H ) − o ( n 2 ) ≥ n 2 16 − o ( n 2 ) . e(V_2,V_3)=e(V_2,L)-e(V_2,V_1)\ge|V_2|\cdot\delta^{+}(H)-o(n^2)\ge\frac{n^2}{16}-o(n^2). e ( V 2 , V 3 ) = e ( V 2 , L ) − e ( V 2 , V 1 ) ≥ ∣ V 2 ∣ ⋅ δ + ( H ) − o ( n 2 ) ≥ 16 n 2 − o ( n 2 ) .
This reasoning can be continued until we obtain:
e ( V 1 , V 2 ) = n 2 16 − o ( n 2 ) e ( V 2 , V 1 ) = o ( n 2 ) e ( V 2 , V 3 ) = n 2 16 − o ( n 2 ) e ( V 3 , V 2 ) = o ( n 2 ) e ( V 3 , V 4 ) = n 2 16 − o ( n 2 ) e ( V 4 , V 3 ) = o ( n 2 ) e ( V 4 , V 1 ) = n 2 16 − o ( n 2 ) e ( V 1 , V 4 ) = o ( n 2 ) \begin{aligned}
e(V_1,V_2)&=\frac{n^2}{16}-o(n^2) & e(V_2,V_1)&=o(n^2)\\
e(V_2,V_3)&=\frac{n^2}{16}-o(n^2) & e(V_3,V_2)&=o(n^2)\\
e(V_3,V_4)&=\frac{n^2}{16}-o(n^2) & e(V_4,V_3)&=o(n^2)\\
e(V_4,V_1)&=\frac{n^2}{16}-o(n^2) & e(V_1,V_4)&=o(n^2)
\end{aligned} e ( V 1 , V 2 ) e ( V 2 , V 3 ) e ( V 3 , V 4 ) e ( V 4 , V 1 ) = 16 n 2 − o ( n 2 ) = 16 n 2 − o ( n 2 ) = 16 n 2 − o ( n 2 ) = 16 n 2 − o ( n 2 ) e ( V 2 , V 1 ) e ( V 3 , V 2 ) e ( V 4 , V 3 ) e ( V 1 , V 4 ) = o ( n 2 ) = o ( n 2 ) = o ( n 2 ) = o ( n 2 )
We found a partition of V ′ V' V ′ := V 1 ∪ V 2 ∪ V 3 ∪ V 4 V_1 \cup V_2 \cup V_3 \cup V_4 V 1 ∪ V 2 ∪ V 3 ∪ V 4 which is close to the blob structure of a blow-up of C ⃗ 4 \vec{C}_4 C 4 , but we do not know anything about its minimum semidegree yet. We need to once again refine the partition.
Denote b : = e H ( V 2 , V 1 ) + e H ( V 3 , V 2 ) + e H ( V 4 , V 3 ) + e H ( V 1 , V 4 ) b := e_H(V_2,V_1)+e_H(V_3,V_2)+e_H(V_4,V_3)+e_H(V_1,V_4) b := e H ( V 2 , V 1 ) + e H ( V 3 , V 2 ) + e H ( V 4 , V 3 ) + e H ( V 1 , V 4 ) (the number of ‘backward arcs’ in H H H ). We know that b = o ( n 2 ) b=o(n^2) b = o ( n 2 ) .
Claim 4.13. Let ε > 0 \varepsilon>0 ε > 0 . There exists ε 1 > 0 \varepsilon_1>0 ε 1 > 0 such that whenever δ ± ( H ) ≥ n 4 ( 1 − ε 1 ) \delta^{\pm}(H)\ge\frac{n}{4}(1-\varepsilon_1) δ ± ( H ) ≥ 4 n ( 1 − ε 1 ) and b ≤ ε 1 n 2 b\le\varepsilon_1n^2 b ≤ ε 1 n 2 , one can remove at most ε n \varepsilon n ε n vertices and at most ε n 2 \varepsilon n^2 ε n 2 arcs from H H H so that the obtained graph H ′ H' H ′ is homomorphic to C ⃗ 4 \vec{C}_4 C 4 and δ ± ( H ′ ) ≥ n 4 − ε n \delta^{\pm}(H')\ge\frac{n}{4}-\varepsilon n δ ± ( H ′ ) ≥ 4 n − ε n . In other words, one can remove o ( n 2 ) o(n^2) o ( n 2 ) arcs and o ( n ) o(n) o ( n ) vertices from H H H so that the obtained graph is homomorphic to C ⃗ 4 \vec{C}_4 C 4 and has minimum semidegree at least n 4 − o ( n ) \frac{n}{4}-o(n) 4 n − o ( n ) .
Proof. Let ε 1 = ε 2 16 \varepsilon_1=\frac{\varepsilon^2}{16} ε 1 = 16 ε 2 . We analyze the arcs which do not agree with the V 1 , … , V 4 V_1,\ldots,V_4 V 1 , … , V 4 blob structure. Take any vertex v ∈ V ( H ) v\in V(H) v ∈ V ( H ) and let v ∈ V i v\in V_i v ∈ V i . Let b 1 ( v ) b_1(v) b 1 ( v ) denote the number of arcs from v v v to V i − 1 V_{i-1} V i − 1 and b 2 ( v ) b_2(v) b 2 ( v ) denote the number of arcs from V i + 1 V_{i+1} V i + 1 to v v v . Since every backward arc is counted once in ∑ v ∈ V ′ b 1 ( v ) \sum_{v\in V'}b_1(v) ∑ v ∈ V ′ b 1 ( v ) and once in ∑ v ∈ V ′ b 2 ( v ) \sum_{v\in V'}b_2(v) ∑ v ∈ V ′ b 2 ( v ) , we know that ∑ v ∈ V ′ ( b 1 ( v ) + b 2 ( v ) ) = 2 b ≤ 2 ε 1 n 2 \sum_{v\in V'}(b_1(v)+b_2(v))=2b\le2\varepsilon_1n^2 ∑ v ∈ V ′ ( b 1 ( v ) + b 2 ( v )) = 2 b ≤ 2 ε 1 n 2 .
Consider the set T ′ T' T ′ of ε n 2 \frac{\varepsilon n}{2} 2 ε n vertices with the largest values of b ( v ) : = b 1 ( v ) + b 2 ( v ) b(v):=b_1(v)+b_2(v) b ( v ) := b 1 ( v ) + b 2 ( v ) . Denoting s : = min v ∈ T ′ b ( v ) s:=\min_{v\in T'}b(v) s := min v ∈ T ′ b ( v ) , we have
ε n 2 ⋅ s ≤ ∑ v ∈ T ′ b ( v ) ≤ ∑ v ∈ V ′ b ( v ) ≤ 2 ε 1 n 2 = ε 2 8 n 2 . \frac{\varepsilon n}{2}\cdot s\le\sum_{v\in T'}b(v)\le\sum_{v\in V'}b(v)\le2\varepsilon_1n^2=\frac{\varepsilon^2}{8}n^2. 2 ε n ⋅ s ≤ v ∈ T ′ ∑ b ( v ) ≤ v ∈ V ′ ∑ b ( v ) ≤ 2 ε 1 n 2 = 8 ε 2 n 2 .
It follows that s ≤ ε n 4 s\le\frac{\varepsilon n}{4} s ≤ 4 ε n .
We now consider the subgraph H ′ H' H ′ on vertex set V ′ ∖ T ′ V'\setminus T' V ′ ∖ T ′ and with all arcs of kind V i → V i + 1 V_i\to V_{i+1} V i → V i + 1 . Clearly, H ′ H' H ′ is homomorphic to C ⃗ 4 \vec{C}_4 C 4 . Moreover, every vertex v ∈ V ′ ∖ T ′ v\in V'\setminus T' v ∈ V ′ ∖ T ′ satisfies b ( v ) ≤ s b(v)\le s b ( v ) ≤ s , which gives
δ ± ( H ′ ) ≥ δ ± ( H ) − ∣ T ′ ∣ − s ≥ n 4 − ε 1 n 4 − ε n 2 − ε n 4 ≥ n 4 − ε n . \delta^{\pm}(H')\ge\delta^{\pm}(H)-|T'|-s\ge\frac{n}{4}-\frac{\varepsilon_1n}{4}-\frac{\varepsilon n}{2}-\frac{\varepsilon n}{4}\ge\frac{n}{4}-\varepsilon n. δ ± ( H ′ ) ≥ δ ± ( H ) − ∣ T ′ ∣ − s ≥ 4 n − 4 ε 1 n − 2 ε n − 4 ε n ≥ 4 n − ε n .
We removed at most ε 2 n < ε n \frac{\varepsilon}{2}n<\varepsilon n 2 ε n < ε n vertices and at most b ≤ ε n 2 b\le\varepsilon n^2 b ≤ ε n 2 arcs from H H H , thus conditions of the claim are met. □
The graph H ′ H' H ′ from Claim 4.13 satisfies the conditions of Lemma 4.6 and finishes its proof. □
Framework for building cycles
For any ℓ > 20 k 2 \ell>20k^2 ℓ > 20 k 2 divisible by 3 3 3 , consider a C ⃗ ℓ \vec{C}_{\ell} C ℓ -free oriented graph G G G with δ + ( G ) > n k \delta^+(G)>\frac{n}{k} δ + ( G ) > k n . By Lemma 4.2 or Lemma 4.6 we know that G G G contains a (not necessarily induced) subgraph H H H homomorphic to C ⃗ k \vec{C}_k C k satisfying δ ± ( H ) ≥ n k − o ( n ) \delta^{\pm}(H)\ge\frac{n}{k}-o(n) δ ± ( H ) ≥ k n − o ( n ) . Denote the blobs of H H H as V 1 , … , V k V_1,\ldots,V_k V 1 , … , V k in the cyclic order and V ′ : = V 1 ∪ … ∪ V k V':=V_1\cup\ldots\cup V_k V ′ := V 1 ∪ … ∪ V k . Since each blob contains the outneighborhood in H H H of a vertex of the preceding blob, we have ∣ V i ∣ ≥ n k − o ( n ) |V_i|\ge\frac{n}{k}-o(n) ∣ V i ∣ ≥ k n − o ( n ) for every i i i , and hence also ∣ V i ∣ ≤ n − ( k − 1 ) ( n k − o ( n ) ) = n k + o ( n ) |V_i|\le n-(k-1)\left(\frac{n}{k}-o(n)\right)=\frac{n}{k}+o(n) ∣ V i ∣ ≤ n − ( k − 1 ) ( k n − o ( n ) ) = k n + o ( n ) .
Consider how H H H is embedded in G G G . The graph G [ V ′ ] G[V'] G [ V ′ ] might contain arcs which do not go from V i V_i V i to V i + 1 V_{i+1} V i + 1 . Call these extra arcs . Moreover, let T : = V ( G ) ∖ V ′ T:=V(G)\setminus V' T := V ( G ) ∖ V ′ denote the set of extra vertices . As ∣ V ′ ∣ ≥ n − o ( n ) |V'|\ge n-o(n) ∣ V ′ ∣ ≥ n − o ( n ) , we know that ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) .
Unless specified otherwise, neighborhoods are considered in the graph G G G .
Observation 4.14. For any x ∈ V i x\in V_i x ∈ V i , y ∈ V i + 2 y\in V_{i+2} y ∈ V i + 2 (indices taken modulo k k k ),
∣ N + ( x ) ∩ N − ( y ) ∩ V i + 1 ∣ ≥ n k − o ( n ) . \left|N^+(x)\cap N^-(y)\cap V_{i+1}\right|\ge\frac{n}{k}-o(n). N + ( x ) ∩ N − ( y ) ∩ V i + 1 ≥ k n − o ( n ) .
Proof. Since N H + ( x ) , N H − ( y ) ⊆ V i + 1 N_H^+(x), N_H^-(y) \subseteq V_{i+1} N H + ( x ) , N H − ( y ) ⊆ V i + 1 , d H + ( x ) , d H − ( y ) ≥ n k − o ( n ) d_H^+(x), d_H^-(y) \ge\frac{n}{k} - o(n) d H + ( x ) , d H − ( y ) ≥ k n − o ( n ) , and ∣ V i + 1 ∣ ≤ n k + o ( n ) |V_{i+1}| \le\frac{n}{k} + o(n) ∣ V i + 1 ∣ ≤ k n + o ( n ) ,
∣ N H + ( x ) ∩ N H − ( y ) ∩ V i + 1 ∣ ≥ d H + ( x ) + d H − ( y ) − ∣ V i + 1 ∣ ≥ ( n k − o ( n ) ) + ( n k − o ( n ) ) − ( n k + o ( n ) ) = n k − o ( n ) . \begin{aligned}
|N_H^+(x) \cap N_H^-(y) \cap V_{i+1}| \ge d_H^+(x) + d_H^-(y) - |V_{i+1}| \\
&\ge\left(\frac{n}{k} - o(n)\right) + \left(\frac{n}{k} - o(n)\right) - \left(\frac{n}{k} + o(n)\right) = \frac{n}{k} - o(n).
\end{aligned} ∣ N H + ( x ) ∩ N H − ( y ) ∩ V i + 1 ∣ ≥ d H + ( x ) + d H − ( y ) − ∣ V i + 1 ∣ ≥ ( k n − o ( n ) ) + ( k n − o ( n ) ) − ( k n + o ( n ) ) = k n − o ( n ) .
Since H H H is a subgraph of G G G , the same bound holds for the neighborhoods taken in G G G .
Observation 4.15. For any x ∈ V i x \in V_i x ∈ V i , y ∈ V j y \in V_j y ∈ V j , x ≠ y x \ne y x = y , there exists a directed path from x x x to y y y in H H H of length at most k + 1 k+1 k + 1 .
Proof. Take x x x and greedily build a sequence x 0 = x x_0=x x 0 = x , x 1 ∈ N H + ( x 0 ) x_1 \in N_H^+(x_0) x 1 ∈ N H + ( x 0 ) , x 2 ∈ N H + ( x 1 ) , … x_2 \in N_H^+(x_1), \ldots x 2 ∈ N H + ( x 1 ) , … , until we reach a vertex x ′ x' x ′ in V j − 2 V_{j-2} V j − 2 (clearly, this will happen after at most k − 1 k-1 k − 1 steps). Now apply Observation 4.14 to conclude there is a path of length 2 from x ′ x' x ′ to y y y , which, together with the previous vertices, forms a walk of length at most k + 1 k+1 k + 1 . Observe that at each step we had at least n k − o ( n ) \frac{n}{k} - o(n) k n − o ( n ) vertices to choose from, which means we can easily ensure that no vertex repeats on the directed walk.
The degree condition δ + ( G ) > n k \delta^+(G) > \frac{n}{k} δ + ( G ) > k n forces G G G to contain elements which do not follow the blow-up structure of H H H . These can be used when traversing the blobs of H H H to build a cycle of length not divisible by k k k . The definition below formalizes this concept.
Definition 4.16. A detour is any directed path P P P in G G G which starts in V i V_i V i and ends in V j V_j V j for some indices i , j i,j i , j . If the length of P P P is d d d , then the remainder of P P P is i − j + d m o d k i-j+d \bmod k i − j + d mod k . A detour is non-zero if its remainder is not 0.
Note that an extra arc is also a non-zero detour. The following observation will allow us to connect detours in order to obtain a cycle of length ℓ \ell ℓ .
Observation 4.17. Let P \mathcal{P} P be a collection of less than k k k pairwise vertex-disjoint detours in G G G , whose sum of lengths is at most 3 k 3k 3 k . If the sum of remainders of elements of P \mathcal{P} P is ℓ m o d k \ell\bmod k ℓ mod k , then the elements of P \mathcal{P} P can be combined with arcs of H H H into a C ⃗ ℓ \vec{C}_{\ell} C ℓ .
Proof. Let P = { P 1 , P 2 , … , P a } \mathcal{P} = \{P_1, P_2, \ldots, P_a\} P = { P 1 , P 2 , … , P a } . Denote the first vertex on the path P i P_i P i as u i u_i u i and the last vertex of P i P_i P i as v i v_i v i . Now apply Observation 4.15 to the pairs ( v 1 , u 2 ) , ( v 2 , u 3 ) , … , ( v a , u 1 ) (v_1,u_2),(v_2,u_3),\ldots,(v_a,u_1) ( v 1 , u 2 ) , ( v 2 , u 3 ) , … , ( v a , u 1 ) to connect the paths in P \mathcal{P} P . Recall that for each of the ‘linking’ vertices we had at least n k − o ( n ) \frac{n}{k} - o(n) k n − o ( n ) possibilities to choose from. In particular, we can pick them to be pairwise distinct and disjoint from P \mathcal{P} P . We obtain a directed cycle C C C , denote its length by d d d . Since each linking path lies in H H H , its length is congruent modulo k k k to the difference of the indices of the blobs it joins, and therefore d ≡ ℓ m o d k d \equiv\ell\bmod k d ≡ ℓ mod k . Moreover,
d ≤ ∣ P ∣ ⋅ ( k + 1 ) + 3 k < k 2 + 4 k < ℓ , d \le|\mathcal{P}| \cdot(k+1) + 3k < k^2 + 4k < \ell, d ≤ ∣ P ∣ ⋅ ( k + 1 ) + 3 k < k 2 + 4 k < ℓ ,
because for even ℓ \ell ℓ we have ℓ > 20 k 2 \ell> 20k^2 ℓ > 20 k 2 , while for odd ℓ \ell ℓ we know that k = 4 k=4 k = 4 and ℓ > 90 > 32 \ell> 90 > 32 ℓ > 90 > 32 . It now suffices to extend C C C until it has length ℓ \ell ℓ .
Perform as many times as needed the following operation. Find in C C C an arc x y xy x y which agrees with the blob structure (i.e. belongs to H H H ); such an arc must exist due to how we constructed the linking paths in Observation 4.15 . Now replace the arc x y xy x y in C C C with the sequence x w 1 w 2 … w k y xw_1w_2\ldots w_ky x w 1 w 2 … w k y , where w 1 ∈ N H + ( x ) ∖ C w_1 \in N_H^+(x) \setminus C w 1 ∈ N H + ( x ) ∖ C , w 2 ∈ N H + ( w 1 ) ∖ C w_2 \in N_H^+(w_1) \setminus C w 2 ∈ N H + ( w 1 ) ∖ C , etc. This clearly extends the length of the cycle C C C by k k k .
This observation allows us to get rid of all extra arcs, simplifying the structure of G [ V ′ ] G[V'] G [ V ′ ] . Note that an extra arc x y xy x y with x ∈ V i , y ∈ V j x \in V_i,y \in V_j x ∈ V i , y ∈ V j constitutes a non-zero detour of remainder i − j + 1 m o d k i-j+1 \bmod k i − j + 1 mod k .
Observation 4.18. By moving at most 2 ( k − 2 ) 2(k-2) 2 ( k − 2 ) vertices from V ′ V' V ′ to T T T , one can ensure that every arc of G [ V ′ ] G[V'] G [ V ′ ] leads from some V i V_i V i to V i + 1 V_{i+1} V i + 1 . The resulting partition still satisfies δ + ( G [ V ′ ] ) ≥ n k − o ( n ) \delta^+(G[V']) \ge\frac{n}{k}-o(n) δ + ( G [ V ′ ]) ≥ k n − o ( n ) and ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) .
Proof. Assume first that G G G contains k − 1 k-1 k − 1 pairwise vertex-disjoint extra arcs. Each of them creates a detour of non-zero remainder. If ℓ \ell ℓ is even, then by Corollary 2.4 we can choose a subset of these arcs whose corresponding remainders sum up to ℓ \ell ℓ mod k k k . These are fewer than k k k pairwise vertex-disjoint detours, so by Observation 4.17 the graph G G G would contain a C → ℓ \overrightarrow{C}_{\ell} C ℓ , a contradiction. Hence, consider odd ℓ \ell ℓ , so k = 4 k=4 k = 4 , and check how the remainders of the 3 extra arcs can be distributed. None of the remainders is equal to ℓ \ell ℓ mod 4, as otherwise we have a contradiction by Observation 4.17 . If all three remainders are equal to ℓ + 2 \ell+2 ℓ + 2 mod 4, then their sum is ℓ \ell ℓ mod 4 and again we have a contradiction by Observation 4.17 . Hence, there is a remainder 2. If any of the remaining remainders is ℓ + 2 \ell+2 ℓ + 2 mod 4, then the two sum up to ℓ \ell ℓ mod 4, contradicting Observation 4.17 . Thus, all three extra arcs are creating detours of remainder 2. Apply now Observation 4.12 to the partition of V ( G ) V(G) V ( G ) into V 1 ∪ V 3 V_1\cup V_3 V 1 ∪ V 3 , V 2 ∪ V 4 V_2\cup V_4 V 2 ∪ V 4 and T T T . The path P P P it provides is a detour, and its remainder is odd. This remainder is not ℓ \ell ℓ mod 4, as otherwise Observation 4.17 applied to P P P alone gives a C → ℓ \overrightarrow{C}_{\ell} C ℓ , so it equals ℓ + 2 \ell+2 ℓ + 2 mod 4. As the internal vertices of P P P lie in T T T , only the two endpoints of P P P can meet the six endpoints of our three extra arcs, so at least one of these arcs is vertex-disjoint from P P P . The two remainders sum up to ℓ \ell ℓ mod 4, contradicting Observation 4.17 as previously.
Therefore a maximum collection of pairwise vertex-disjoint extra arcs consists of at most k − 2 k-2 k − 2 arcs, and by maximality every extra arc of G G G meets one of its at most 2 ( k − 2 ) 2(k-2) 2 ( k − 2 ) endpoints. Moving these endpoints from V ′ V' V ′ to T T T thus destroys all extra arcs. As only a constant number of vertices is moved, the bounds on ∣ T ∣ |T| ∣ T ∣ and on the semidegrees of G [ V ′ ] G[V'] G [ V ′ ] are unaffected.
From now on we assume that every arc of G [ V ′ ] G[V'] G [ V ′ ] leads from some V i V_i V i to V i + 1 V_{i+1} V i + 1 . Recall that the set of extra vertices T = V ( G ) ∖ V ′ T=V(G)\setminus V' T = V ( G ) ∖ V ′ satisfies ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) . If a vertex v ∈ T v\in T v ∈ T has an arc from some V i V_i V i and an arc to V j V_j V j (i , j i,j i , j not necessarily distinct), then it forms a detour of length 2 with remainder i − j + 2 i-j+2 i − j + 2 mod k k k . We introduce the following definition to be able to easily connect these detours.
Definition 4.19. A blob V i V_i V i is an in-pointing blob for a vertex t ∈ T t\in T t ∈ T if ∣ N − ( t ) ∩ V i ∣ ≥ 2 k |N^-(t)\cap V_i|\ge2k ∣ N − ( t ) ∩ V i ∣ ≥ 2 k . Similarly, a blob V i V_i V i is out-pointing for some t ∈ T t\in T t ∈ T if ∣ N + ( t ) ∩ V i ∣ ≥ 2 k |N^+(t)\cap V_i|\ge2k ∣ N + ( t ) ∩ V i ∣ ≥ 2 k .
This neighborhood size bound will prove useful when expanding an obtained closed directed walk of length ℓ \ell ℓ into a proper C → ℓ \overrightarrow{C}_{\ell} C ℓ .
Every t ∈ T t\in T t ∈ T has at most 2 k 2 2k^2 2 k 2 arcs into blobs which are not out-pointing for t t t , and similarly, t t t has at most 2 k 2 2k^2 2 k 2 arcs from blobs which are not in-pointing for t t t . Summing this up, we obtain at most 4 k 2 ∣ T ∣ = o ( n ) 4k^2|T|=o(n) 4 k 2 ∣ T ∣ = o ( n ) vertices in V ′ V' V ′ which can be adjacent to T T T , but not within the out- or in-pointing blob relation. Call this set of exceptional vertices X X X . Note that for any i i i , ∣ V i ∖ X ∣ ≥ n k − o ( n ) |V_i\setminus X|\ge\frac{n}{k}-o(n) ∣ V i ∖ X ∣ ≥ k n − o ( n ) .
Definition 4.20. A sidewalk V i → t → V j V_i\to t\to V_j V i → t → V j is a tuple ( V i , t , V j ) (V_i,t,V_j) ( V i , t , V j ) with t ∈ T t\in T t ∈ T , in which V i V_i V i is in-pointing for t t t and V j V_j V j is out-pointing for t t t . The vertex t t t is the center of this sidewalk. The remainder of a sidewalk V i → t → V j V_i\to t\to V_j V i → t → V j is i − j + 2 i-j+2 i − j + 2 mod k k k . A sidewalk is non-zero if its remainder is not 0.
Note that each sidewalk corresponds to many potential detours. The observation below allows us to join sidewalks to a cycle of length ℓ \ell ℓ . In this section we used it only for joining sidewalks, but in Section 5 it will be used also to join sidewalks to a single longer detour.
Observation 4.21. Let S S S be a collection of sidewalks and at most one detour, such that in total there are fewer than k k k elements, centers of all sidewalks are distinct and different from the vertices of the detour, and the detour has length at most k k k and at most 4 vertices from V ′ V' V ′ . If the remainders of the elements of S S S add up to ℓ \ell ℓ mod k k k , then G G G contains a C → ℓ \overrightarrow{C}_{\ell} C ℓ .
Proof. For each sidewalk V i → t → V j V_i \to t \to V_j V i → t → V j in S S S , choose some vertices u t ∈ V i ∩ N − ( t ) u_t \in V_i \cap N^{-}(t) u t ∈ V i ∩ N − ( t ) and w t ∈ V j ∩ N + ( t ) w_t \in V_j \cap N^{+}(t) w t ∈ V j ∩ N + ( t ) , so that all the chosen vertices u t u_t u t , w t w_t w t are pairwise distinct and different from the detour. This is possible since for each sidewalk, ∣ V i ∩ N − ( t ) ∣ ≥ 2 k |V_i \cap N^{-}(t)| \ge2k ∣ V i ∩ N − ( t ) ∣ ≥ 2 k and ∣ V j ∩ N + ( t ) ∣ ≥ 2 k |V_j \cap N^{+}(t)| \ge2k ∣ V j ∩ N + ( t ) ∣ ≥ 2 k , while at each step fewer than 2 k 2k 2 k vertices have to be avoided. As a result, we obtain less than k k k vertex disjoint detours of total length at most 2 ( k − 2 ) + k < 3 k 2(k-2)+k < 3k 2 ( k − 2 ) + k < 3 k , whose remainders add up to ℓ \ell ℓ mod k k k , which allows us to conclude using Observation 4.17 . □ \square □
The proven observation allows us to bound the total number of non-zero sidewalks. Note that a vertex t ∈ T t \in T t ∈ T may be the center of several sidewalks with the same remainder, but we want to count every remainder only once for every center.
Observation 4.22. For every t ∈ T t \in T t ∈ T , let S t S_t S t be the set of non-zero remainders of the sidewalks with center t t t . Then ∑ t ∈ T ∣ S t ∣ ≤ k − 2 \sum_{t \in T} |S_t| \le k-2 ∑ t ∈ T ∣ S t ∣ ≤ k − 2 .
Proof. Assume there is a set of a a a centers t 1 , t 2 , … , t a ∈ T t_1,t_2,\ldots,t_a \in T t 1 , t 2 , … , t a ∈ T and a non-empty sets of remainders R 1 , … , R a ⊆ ( Z k ∖ { 0 } ) R_1,\ldots,R_a \subseteq(\mathbb{Z}_k \setminus\{0\}) R 1 , … , R a ⊆ ( Z k ∖ { 0 }) such that t i t_i t i forms non-zero sidewalks of all the remainders in R i R_i R i , and ∑ i = 1 a ∣ R i ∣ ≥ k − 1 \sum_{i=1}^{a} |R_i| \ge k-1 ∑ i = 1 a ∣ R i ∣ ≥ k − 1 . Discarding remainders if necessary, we may assume that ∑ i = 1 a ∣ R i ∣ = k − 1 \sum_{i=1}^{a} |R_i| = k-1 ∑ i = 1 a ∣ R i ∣ = k − 1 and hence a ≤ k − 1 a \le k-1 a ≤ k − 1 .
For even ℓ \ell ℓ , by Lemma 2.3 we are able to choose at most one remainder from each R i R_i R i so that the chosen remainders sum up to ℓ \ell ℓ mod k k k . The corresponding sidewalks have distinct centers and there are fewer than k k k of them. The obtained set of sidewalks can be used to build a C → ℓ \overrightarrow{C}_{\ell} C ℓ by Observation 4.21 , a contradiction.
For odd ℓ \ell ℓ , so k = 4 k=4 k = 4 , repeatedly using Observation 4.21 we deduce how the remainders are distributed. Firstly, no sidewalk has remainder ℓ \ell ℓ mod 4, so all sidewalks are of remainders 2 or ℓ + 2 \ell+2 ℓ + 2 mod 4 and consequently a ≥ 2 a \ge2 a ≥ 2 . Then, there cannot be sidewalks with distinct centers that have remainders 2 and ℓ + 2 \ell+2 ℓ + 2 mod 4, so all sidewalks have the same remainder and a = 3 a=3 a = 3 . Finally, there are no three sidewalks of remainder ℓ + 2 \ell+2 ℓ + 2 mod 4, thus there are three sidewalks of remainder 2 with distinct centers. Let P P P be the detour given by Observation 4.12 applied to the partition of V ( G ) V(G) V ( G ) into V 1 ∪ V 3 V_1 \cup V_3 V 1 ∪ V 3 , V 2 ∪ V 4 V_2 \cup V_4 V 2 ∪ V 4 and T T T . As in the proof of Observation 4.18 its remainder is ℓ + 2 \ell+2 ℓ + 2 mod 4. Since P P P has at most two internal vertices, the center of one of the previously obtained three sidewalks, say t ∈ T t \in T t ∈ T , does not lie on P P P . By the definition of a sidewalk, t t t has at least 8 inneighbors and outneighbors in the respective blobs, so it creates a detour that is vertex-disjoint from P P P . The remainders of this detour and P P P sum to ℓ \ell ℓ mod 4, which by Observation 4.17 yields a C → ℓ \overrightarrow{C}_{\ell} C ℓ , a contradiction. □ \square □
Conclusion
We can now finish the proof of Theorem 1.4.
Proof of Theorem 1.4. Assuming the contrary, let G G G be a large enough oriented graph on n n n vertices with δ + ( G ) ≥ n k + k − 1 k \delta^{+}(G) \ge\frac{n}{k}+\frac{k-1}{k} δ + ( G ) ≥ k n + k k − 1 not containing a directed cycle of length ℓ > 20 k 2 \ell> 20k^2 ℓ > 20 k 2 divisible by 3. By Lemma 4.2 or Lemma 4.6 and Observation 4.18 , the vertex set of G G G can be partitioned into sets V ′ = V 1 ∪ … ∪ V k V'=V_1 \cup\ldots\cup V_k V ′ = V 1 ∪ … ∪ V k and T T T , such that every arc of G [ V ′ ] G[V'] G [ V ′ ] leads from some V i V_i V i to V i + 1 V_{i+1} V i + 1 , δ + ( G [ V ′ ] ) ≥ n k − o ( n ) \delta^{+}(G[V']) \ge\frac{n}{k}-o(n) δ + ( G [ V ′ ]) ≥ k n − o ( n ) and ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) . We will show that the sets S t S_t S t of non-zero remainders of the sidewalks with center t t t are too large, which leads to a contradiction with Observation 4.22 . For each t ∈ T t \in T t ∈ T , denote by I t I_t I t the set of indices i i i such that V i V_i V i is in-pointing for t t t . Every t ∈ T t \in T t ∈ T has at least one out-pointing blob: indeed d + ( t ) ≥ δ + ( G ) − ∣ T ∣ ≥ n k − o ( n ) d^+(t) \ge\delta^+(G)-|T| \ge\frac{n}{k}-o(n) d + ( t ) ≥ δ + ( G ) − ∣ T ∣ ≥ k n − o ( n ) , so at least one of the k k k blobs receives at least n k 2 − o ( n ) ≥ 2 k \frac{n}{k^2}-o(n) \ge2k k 2 n − o ( n ) ≥ 2 k arcs from t t t . Fixing such a blob V j V_j V j , the ∣ I t ∣ |I_t| ∣ I t ∣ remainders i − j + 2 i-j+2 i − j + 2 of the sidewalks V i → t → V j V_i \to t \to V_j V i → t → V j are pairwise distinct and at most one of them equals 0. Hence ∣ S t ∣ ≥ ∣ I t ∣ − 1 |S_t| \ge|I_t|-1 ∣ S t ∣ ≥ ∣ I t ∣ − 1 for every t ∈ T t \in T t ∈ T .
Consider a sample of k k k vertices w 1 ∈ V 1 ∖ X , w 2 ∈ V 2 ∖ X , … , w k ∈ V k ∖ X w_1 \in V_1 \setminus X, w_2 \in V_2 \setminus X,\ldots,w_k \in V_k \setminus X w 1 ∈ V 1 ∖ X , w 2 ∈ V 2 ∖ X , … , w k ∈ V k ∖ X . For any t ∈ T t \in T t ∈ T , it holds that if there is an arc w i t w_i t w i t , then V i V_i V i is in-pointing for t t t . Moreover, since every arc of G [ V ′ ] G[V'] G [ V ′ ] leads from some V i V_i V i to V i + 1 V_{i+1} V i + 1 , we know that N + ( w i ) ⊆ ( V i + 1 ∪ T ) N^+(w_i) \subseteq(V_{i+1} \cup T) N + ( w i ) ⊆ ( V i + 1 ∪ T ) . Therefore,
n + k − 1 ≤ k ⋅ δ + ( G ) ≤ ∑ i = 1 k d + ( w i ) = ∑ i = 1 k ( ∣ N + ( w i ) ∩ V i + 1 ∣ + ∣ N + ( w i ) ∩ T ∣ ) ≤ ∑ i = 1 k ∣ V i + 1 ∣ + ∑ t ∈ T ∣ I t ∣ = ( n − ∣ T ∣ ) + ∑ t ∈ T ∣ I t ∣ = n + ∑ t ∈ T ( ∣ I t ∣ − 1 ) . (1) \begin{aligned}
n+k-1 \le k\cdot\delta^+(G) \le\sum_{i=1}^{k}d^+(w_i)=\sum_{i=1}^{k}\left(\left|N^+(w_i)\cap V_{i+1}\right|+\left|N^+(w_i)\cap T\right|\right) \\
&\le\sum_{i=1}^{k}|V_{i+1}|+\sum_{t\in T}|I_t|=(n-|T|)+\sum_{t\in T}|I_t|=n+\sum_{t\in T}(|I_t|-1). \tag*{(1)}
\end{aligned} n + k − 1 ≤ k ⋅ δ + ( G ) ≤ i = 1 ∑ k d + ( w i ) = i = 1 ∑ k ( N + ( w i ) ∩ V i + 1 + N + ( w i ) ∩ T ) ≤ i = 1 ∑ k ∣ V i + 1 ∣ + t ∈ T ∑ ∣ I t ∣ = ( n − ∣ T ∣ ) + t ∈ T ∑ ∣ I t ∣ = n + t ∈ T ∑ ( ∣ I t ∣ − 1 ) . (1)
This implies that ∑ t ∈ T ∣ S t ∣ ≥ ∑ t ∈ T ( ∣ I t ∣ − 1 ) ≥ k − 1 \sum_{t\in T}|S_t|\ge\sum_{t\in T}(|I_t|-1)\ge k-1 ∑ t ∈ T ∣ S t ∣ ≥ ∑ t ∈ T ( ∣ I t ∣ − 1 ) ≥ k − 1 . This contradicts Observation 4.22 and finishes the proof of Theorem 1.4 .
Special cases
Theorem 1.4 is not tight for four families of lengths, for which the optimal outdegree bound is determined by Theorem 1.5. Together with the constructions of § 3 , Theorem 1.5 is directly implied by the following theorem.
Theorem 5.1. Let ℓ \ell ℓ be an integer divisible by 3 and k k k be the smallest integer greater than 2 that does not divide ℓ \ell ℓ , such that ( k , ℓ m o d k ) ∈ { ( 4 , 2 ) , ( 4 , 3 ) , ( 5 , 3 ) , ( 5 , 4 ) } (k,\ell\bmod k)\in\{(4,2),(4,3),(5,3),(5,4)\} ( k , ℓ mod k ) ∈ {( 4 , 2 ) , ( 4 , 3 ) , ( 5 , 3 ) , ( 5 , 4 )} . Assume that ℓ > 20 k 2 \ell>20k^2 ℓ > 20 k 2 and put
c : = { k − 3 if ℓ m o d k = 3 , k − 2 if ℓ m o d k ≠ 3. c :=
\begin{cases}
k-3 & \text{if }\ell\bmod k=3,\\
k-2 & \text{if }\ell\bmod k\ne3.
\end{cases} c := { k − 3 k − 2 if ℓ mod k = 3 , if ℓ mod k = 3. Then every oriented graph G G G on n n n vertices, with n n n large enough, satisfying δ + ( G ) ≥ n + c k \delta^+(G)\ge\frac{n+c}{k} δ + ( G ) ≥ k n + c contains a directed cycle of length ℓ \ell ℓ .
Throughout the section we assume, aiming at a contradiction, that G G G is a C ℓ → \overrightarrow{C_\ell} C ℓ -free oriented graph on n n n vertices with δ + ( G ) ≥ n + c k \delta^+(G)\ge\frac{n+c}{k} δ + ( G ) ≥ k n + c . In particular δ + ( G ) > n k \delta^+(G)>\frac{n}{k} δ + ( G ) > k n , so we may use everything proved in Subsection 4.3. We fix the partition V ( G ) = V ′ ∪ T V(G)=V'\cup T V ( G ) = V ′ ∪ T with V ′ = V 1 ∪ ⋯ ∪ V k V'=V_1\cup\cdots\cup V_k V ′ = V 1 ∪ ⋯ ∪ V k provided by Lemma 4.2 or Lemma 4.6 together with Observation 4.18 , so that every arc of G [ V ′ ] G[V'] G [ V ′ ] leads from some V i V_i V i to V i + 1 V_{i+1} V i + 1 , δ ± ( G [ V ′ ] ) ≥ n k − o ( n ) \delta^\pm(G[V'])\ge\frac{n}{k}-o(n) δ ± ( G [ V ′ ]) ≥ k n − o ( n ) and ∣ T ∣ = o ( n ) |T|=o(n) ∣ T ∣ = o ( n ) . We keep the in-pointing and out-pointing relations of Definition 4.19 , the sidewalks of Definition 4.20 and the exceptional set X ⊆ V ′ X\subseteq V' X ⊆ V ′ with ∣ X ∣ = o ( n ) |X|=o(n) ∣ X ∣ = o ( n ) . Recall that any adjacency between a vertex t ∈ T t\in T t ∈ T and a vertex of V i ∖ X V_i\setminus X V i ∖ X witnesses the corresponding pointing relation, and that ∣ V i ∖ X ∣ ≥ n k − o ( n ) |V_i\setminus X|\ge\frac{n}{k}-o(n) ∣ V i ∖ X ∣ ≥ k n − o ( n ) .
Admissible sidewalk remainders
Contrary to the proof of Theorem 1.4, now the inequalities in (1) with the weaker bound δ + ( G ) ≥ n + c k \delta^+(G)\ge\frac{n+c}{k} δ + ( G ) ≥ k n + c will not provide k − 1 k-1 k − 1 non-zero sidewalks. We need to do more careful analysis. Because of that, we define quantities that measure how “irregular” the vertices in T T T and the blobs in V ′ V' V ′ behave.
For t ∈ T t\in T t ∈ T we define I t I_t I t as the set of indices i i i such that V i V_i V i is in-pointing for t t t , and O t O_t O t as the set of indices j j j such that t t t has an outneighbor in V j ∖ X V_j\setminus X V j ∖ X . Note that this is a bit stronger property than just V j V_j V j is an out-pointing blob for t t t . Nevertheless, by the definition of X X X , every such V j V_j V j is out-pointing for t t t . Let R t R_t R t be the set of non-zero remainders of the sidewalks V i → t → V j V_i \to t \to V_j V i → t → V j with i ∈ I t i \in I_t i ∈ I t and j ∈ O t j \in O_t j ∈ O t , that is
R t = ( I t − O t + 2 ) ∖ { 0 } , R_t = (I_t - O_t + 2) \setminus\{0\}, R t = ( I t − O t + 2 ) ∖ { 0 } ,
and let
ε t = ∣ R t ∣ − ∣ I t ∣ + 1. \varepsilon_t = |R_t| - |I_t| + 1. ε t = ∣ R t ∣ − ∣ I t ∣ + 1.
Since t t t has at least δ + ( G ) − ∣ T ∣ − ∣ X ∣ > 0 \delta^{+}(G)-|T|-|X| > 0 δ + ( G ) − ∣ T ∣ − ∣ X ∣ > 0 outneighbors in V ′ ∖ X V'\setminus X V ′ ∖ X , the set O t O_t O t is non-empty, so ε t ≥ 0 \varepsilon_t \ge0 ε t ≥ 0 and ε t \varepsilon_t ε t measures how many additional non-zero remainders t t t creates. In particular, ε t = 0 \varepsilon_t = 0 ε t = 0 implies that I t − j + 2 = R t ∪ { 0 } I_t-j+2 = R_t \cup\{0\} I t − j + 2 = R t ∪ { 0 } for every j ∈ O t j \in O_t j ∈ O t , that is, t t t together with V j V_j V j and all its in-pointing blobs creates sidewalks of all remainders in R t ∪ { 0 } R_t \cup\{0\} R t ∪ { 0 } .
While for i ∈ { 1 , 2 , … , k } i \in\{1,2,\ldots,k\} i ∈ { 1 , 2 , … , k } let T i T_i T i be the set of vertices in T T T , for which V i V_i V i is an in-pointing blob, that is,
T i = { t ∈ T : i ∈ I t } T_i = \{t \in T : i \in I_t\} T i = { t ∈ T : i ∈ I t }
and let
μ i = ∣ V i + 1 ∣ + ∣ T i ∣ − δ + ( G ) . \mu_i = |V_{i+1}| + |T_i| - \delta^{+}(G). μ i = ∣ V i + 1 ∣ + ∣ T i ∣ − δ + ( G ) .
Since each vertex in V i ∖ X V_i \setminus X V i ∖ X has all its outneighbors in V i + 1 V_{i+1} V i + 1 or in T i T_i T i , we have μ i ≥ 0 \mu_i \ge0 μ i ≥ 0 , and μ i \mu_i μ i measures how much room is left. In particular, μ i = 0 \mu_i = 0 μ i = 0 implies that every vertex in V i ∖ X V_i \setminus X V i ∖ X has an arc to every vertex in V i + 1 V_{i+1} V i + 1 and to all vertices t ∈ T t \in T t ∈ T , for which V i V_i V i is in-pointing.
Summing up the defined measures over all blobs and vertices in T T T , we obtain
0 ≤ ∑ i = 1 k μ i + ∑ t ∈ T ε t = ( n − ∣ T ∣ + ∑ t ∈ T ∣ I t ∣ − k δ + ( G ) ) + ( ∑ t ∈ T ∣ R t ∣ − ∑ t ∈ T ∣ I t ∣ + ∣ T ∣ ) = ∑ t ∈ T ∣ R t ∣ + n − k δ + ( G ) ≤ ∑ t ∈ T ∣ R t ∣ − c . \begin{aligned}
0 &\le\sum_{i=1}^{k} \mu_i + \sum_{t\in T} \varepsilon_t \\
&= \left(n-|T|+\sum_{t\in T}|I_t|-k\delta^{+}(G)\right)+\left(\sum_{t\in T}|R_t|-\sum_{t\in T}|I_t|+|T|\right)\\
&= \sum_{t\in T}|R_t|+n-k\delta^{+}(G)\le\sum_{t\in T}|R_t|-c.
\end{aligned} 0 ≤ i = 1 ∑ k μ i + t ∈ T ∑ ε t = ( n − ∣ T ∣ + t ∈ T ∑ ∣ I t ∣ − k δ + ( G ) ) + ( t ∈ T ∑ ∣ R t ∣ − t ∈ T ∑ ∣ I t ∣ + ∣ T ∣ ) = t ∈ T ∑ ∣ R t ∣ + n − k δ + ( G ) ≤ t ∈ T ∑ ∣ R t ∣ − c .
Thus, ∑ t ∈ T ∣ R t ∣ ≥ c \sum_{t\in T}|R_t| \ge c ∑ t ∈ T ∣ R t ∣ ≥ c . On the other hand, as R t ⊆ S t R_t \subseteq S_t R t ⊆ S t , by Observation 4.22 , we have ∑ t ∈ T ∣ R t ∣ ≤ k − 2 \sum_{t\in T}|R_t| \le k-2 ∑ t ∈ T ∣ R t ∣ ≤ k − 2 . Since c = k − 2 c=k-2 c = k − 2 or k − 3 k-3 k − 3 , we have that
∑ i = 1 k μ i + ∑ t ∈ T ε t ∈ { 0 , 1 } (2) \sum_{i=1}^{k}\mu_i+\sum_{t\in T}\varepsilon_t\in\{0,1\} \tag*{(2)} i = 1 ∑ k μ i + t ∈ T ∑ ε t ∈ { 0 , 1 } (2)
and ∑ t ∈ T ∣ R t ∣ \sum_{t\in T}|R_t| ∑ t ∈ T ∣ R t ∣ is equal to k − 2 k-2 k − 2 or k − 3 k-3 k − 3 . Note that ∑ t ∈ T ∣ R t ∣ = k − 3 \sum_{t\in T}|R_t|=k-3 ∑ t ∈ T ∣ R t ∣ = k − 3 is possible only when c = k − 3 c=k-3 c = k − 3 , that is when ℓ m o d k = 3 \ell\bmod k=3 ℓ mod k = 3 , and it forces all μ i = 0 \mu_i=0 μ i = 0 and all ε t = 0 \varepsilon_t=0 ε t = 0 . Therefore, depending on the considered value of ℓ \ell ℓ and k k k , and the value of ∑ t ∈ T ∣ R t ∣ \sum_{t\in T}|R_t| ∑ t ∈ T ∣ R t ∣ , we have 6 possible cases. They are listed in Table 3 . Before we analyze those cases in detail, we make some observations on possible sidewalk remainders that allow us to list all possible non-empty sets R t R_t R t in each case.
Table 3. All possible families of the non-empty sets R t R_t R t .
Observation 5.2. If i ∈ I t ∩ O t i\in I_t\cap O_t i ∈ I t ∩ O t for some t ∈ T t\in T t ∈ T , that is, 2 ∈ R t 2\in R_t 2 ∈ R t , then μ i = 1 \mu_i=1 μ i = 1 .
Proof. By the definition of O t O_t O t , there exists an arc t v tv t v for some vertex v ∈ V i ∖ X v\in V_i\setminus X v ∈ V i ∖ X . Since all outneighbors of v v v lie in V i + 1 V_{i+1} V i + 1 or in T i ∖ { t } T_i\setminus\{t\} T i ∖ { t } ,
δ + ( G ) ≤ d + ( v ) ≤ ∣ V i + 1 ∣ + ∣ T i ∣ − 1 = δ + ( G ) + μ i − 1 , \delta^{+}(G)\le d^{+}(v)\le|V_{i+1}|+|T_i|-1=\delta^{+}(G)+\mu_i-1, δ + ( G ) ≤ d + ( v ) ≤ ∣ V i + 1 ∣ + ∣ T i ∣ − 1 = δ + ( G ) + μ i − 1 ,
so μ i ≥ 1 \mu_i\ge1 μ i ≥ 1 and μ i = 1 \mu_i=1 μ i = 1 by (2). □ \square □
Observation 5.3. If ε t = 0 \varepsilon_t=0 ε t = 0 for some t ∈ T t\in T t ∈ T , then ∣ O t ∣ = 1 |O_t|=1 ∣ O t ∣ = 1 . Proof. Assumption ε t = 0 \varepsilon_t = 0 ε t = 0 means that for every j ∈ O t j \in O_t j ∈ O t there are ∣ I t ∣ = ∣ R t ∣ + 1 |I_t| = |R_t| + 1 ∣ I t ∣ = ∣ R t ∣ + 1 distinct remainders i − j + 2 i-j+2 i − j + 2 in R t ∪ { 0 } R_t \cup\{0\} R t ∪ { 0 } , so I t − j + 2 = R t ∪ { 0 } I_t-j+2 = R_t \cup\{0\} I t − j + 2 = R t ∪ { 0 } . This implies that if there are two distinct j , j ′ ∈ O t j,j' \in O_t j , j ′ ∈ O t , then R t ∪ { 0 } = ( R t ∪ { 0 } ) + ( j ′ − j ) R_t \cup\{0\} = (R_t \cup\{0\}) + (j'-j) R t ∪ { 0 } = ( R t ∪ { 0 }) + ( j ′ − j ) , so R t ∪ { 0 } R_t \cup\{0\} R t ∪ { 0 } contains the subgroup generated by j ′ − j j'-j j ′ − j . Among the considered cases, there is only one non-trivial subgroup of Z k \mathbb{Z}_k Z k that does not contain ℓ m o d k \ell\bmod k ℓ mod k , that is { 0 , 2 } \{0,2\} { 0 , 2 } in the case k = 4 k=4 k = 4 and ℓ m o d k = 3 \ell\bmod k=3 ℓ mod k = 3 . But then, R t ∪ { 0 } R_t \cup\{0\} R t ∪ { 0 } contains { 0 , 2 } \{0,2\} { 0 , 2 } , is contained in { 0 , 1 , 2 } \{0,1,2\} { 0 , 1 , 2 } , and is invariant under the translation by 2, so it is equal to { 0 , 2 } \{0,2\} { 0 , 2 } . Thus, R t = { 2 } R_t=\{2\} R t = { 2 } , O t = { j , j + 2 } O_t=\{j,j+2\} O t = { j , j + 2 } , and the equality I t − j + 2 = R t ∪ { 0 } I_t-j+2=R_t\cup\{0\} I t − j + 2 = R t ∪ { 0 } gives I t = { j , j + 2 } I_t=\{j,j+2\} I t = { j , j + 2 } . By Observation 5.2, μ j = 1 \mu_j=1 μ j = 1 and μ j + 2 = 1 \mu_{j+2}=1 μ j + 2 = 1 contradicting (2).
The above observations exclude the possibility of having two distinct vertices t , t ′ ∈ T t,t' \in T t , t ′ ∈ T with 2 ∈ R t ∩ R t ′ 2 \in R_t \cap R_{t'} 2 ∈ R t ∩ R t ′ . Indeed, in such a case i ∈ I t ∩ O t i \in I_t \cap O_t i ∈ I t ∩ O t and i ′ ∈ I t ′ ∩ O t ′ i' \in I_{t'} \cap O_{t'} i ′ ∈ I t ′ ∩ O t ′ for some i , i ′ i,i' i , i ′ , so by Observation 5.2, μ i = μ i ′ = 1 \mu_i=\mu_{i'}=1 μ i = μ i ′ = 1 , and (2) implies that i = i ′ i=i' i = i ′ and ε t = ε t ′ = 0 \varepsilon_t=\varepsilon_{t'}=0 ε t = ε t ′ = 0 . Thus, by Observation 5.3, O t = O t ′ = { i } O_t=O_{t'}=\{i\} O t = O t ′ = { i } . Since the outneighbors of t t t and t ′ t' t ′ are only in T T T , X X X and V i ∖ X V_i \setminus X V i ∖ X , each of them has at least δ + ( G ) − ∣ T ∣ − ∣ X ∣ = n k − o ( n ) \delta^+(G)-|T|-|X|=\frac{n}{k}-o(n) δ + ( G ) − ∣ T ∣ − ∣ X ∣ = k n − o ( n ) outneighbors in V i ∖ X V_i \setminus X V i ∖ X , while ∣ V i ∣ ≤ n k + o ( n ) |V_i| \le\frac{n}{k}+o(n) ∣ V i ∣ ≤ k n + o ( n ) . Hence, there is a vertex v ∈ V i ∖ X v \in V_i \setminus X v ∈ V i ∖ X with both arcs t v tv t v and t ′ v t'v t ′ v . All outneighbors of v v v lie in V i + 1 V_{i+1} V i + 1 or in T i ∖ { t , t ′ } T_i \setminus\{t,t'\} T i ∖ { t , t ′ } , so
δ + ( G ) ≤ d + ( v ) ≤ ∣ V i + 1 ∣ + ∣ T i ∣ − 2 = δ + ( G ) + μ i − 2 , \delta^+(G) \le d^+(v) \le|V_{i+1}|+|T_i|-2=\delta^+(G)+\mu_i-2, δ + ( G ) ≤ d + ( v ) ≤ ∣ V i + 1 ∣ + ∣ T i ∣ − 2 = δ + ( G ) + μ i − 2 ,
which means that μ i ≥ 2 \mu_i \ge2 μ i ≥ 2 , contradicting (2).
Therefore, there is at most one vertex t ∈ T t \in T t ∈ T with 2 ∈ R t 2 \in R_t 2 ∈ R t , and it may exist only when ∑ i μ i = 1 \sum_i \mu_i=1 ∑ i μ i = 1 , which means c = k − 3 c=k-3 c = k − 3 and ∑ t ∣ R t ∣ = k − 2 \sum_t |R_t|=k-2 ∑ t ∣ R t ∣ = k − 2 . This, together with Observation 4.21 , allows us to list all possible sets of remainders in each considered case.
Determination of the above possible families is straightforward. As an example, we show the most complex case ( k , ℓ m o d k ) = ( 5 , 3 ) (k,\ell\bmod k)=(5,3) ( k , ℓ mod k ) = ( 5 , 3 ) with ∑ t ∣ R t ∣ = k − 2 = 3 \sum_t |R_t|=k-2=3 ∑ t ∣ R t ∣ = k − 2 = 3 . Assume first that there is a vertex t ∈ T t \in T t ∈ T having remainder 2 in R t R_t R t . As shown above, no other vertex has remainder 2. By Observation 4.21 , no other vertex in T T T has remainder 1, no vertex has remainder 3, and there are no two vertices having remainder 4, so in order to have 3 non-zero remainders, we need to have a single vertex with R t = { 1 , 2 , 4 } R_t=\{1,2,4\} R t = { 1 , 2 , 4 } or one vertex with { 1 , 2 } \{1,2\} { 1 , 2 } and the other with { 4 } \{4\} { 4 } . Whereas, if there is no vertex with remainder 2, then we may have at most two vertices with remainder 1 and at most one with remainder 4, which leads to two possible families depending if the vertices having remainders 1 and 4 are distinct.
By (2) and Observation 5.3, all but at most one vertex t ∈ T t \in T t ∈ T satisfy ∣ O t ∣ = 1 |O_t|=1 ∣ O t ∣ = 1 . This allows us to “assign” every such vertex to an appropriate blob in order to have most of its outneighbors in the consecutive blob. Formally, for any vertex t ∈ T t \in T t ∈ T with O t = { i } O_t=\{i\} O t = { i } , we define the position of t t t as p ( t ) = i − 1 p(t)=i-1 p ( t ) = i − 1 . We also say that any vertex v ∈ V i v \in V_i v ∈ V i has position p ( v ) = i p(v)=i p ( v ) = i . Thus, all but at most one vertex of G G G (possibly the vertex t ∈ T t \in T t ∈ T having ε t = 1 \varepsilon_t=1 ε t = 1 ) has a position. Note that every vertex with a position i i i has all its outneighbors in V i + 1 ∪ X ∪ T V_{i+1} \cup X \cup T V i + 1 ∪ X ∪ T . If ε t = 0 \varepsilon_t=0 ε t = 0 for some t ∈ T t \in T t ∈ T , then I t − p ( t ) + 1 = R t ∪ { 0 } I_t-p(t)+1=R_t \cup\{0\} I t − p ( t ) + 1 = R t ∪ { 0 } , so V p ( t ) − 1 V_{p(t)-1} V p ( t ) − 1 is in-pointing for t t t , and t ∈ T p ( t ) t \in T_{p(t)} t ∈ T p ( t ) if and only if 1 ∈ R t 1 \in R_t 1 ∈ R t .
We will build detours from short paths of vertices with positions. For a directed path v 1 v 2 … v m v_1v_2\ldots v_m v 1 v 2 … v m with m ≤ 3 m \le3 m ≤ 3 of vertices in T ∪ X T \cup X T ∪ X with positions, let V i V_i V i be an in-pointing blob of v 1 v_1 v 1 if v 1 ∈ T v_1 \in T v 1 ∈ T , or i = p ( v 1 ) − 1 i=p(v_1)-1 i = p ( v 1 ) − 1 if v 1 ∈ X v_1 \in X v 1 ∈ X . Adding an inneighbor of v 1 v_1 v 1 in V i V_i V i at the beginning and, if v m ∈ T v_m \in T v m ∈ T , an outneighbor of v m v_m v m in V p ( v m ) + 1 V_{p(v_m)+1} V p ( v m ) + 1 at the end, we obtain a detour of remainder i − p ( v m ) + m i-p(v_m)+m i − p ( v m ) + m with at most four vertices in V ′ V' V ′ , and each added vertex can be chosen in at least 2 k 2k 2 k ways. We say that v 1 , … , v m v_1,\ldots,v_m v 1 , … , v m create a detour of this remainder.
Finalization in the cases with ∑ i μ i + ∑ t ε t = 0 \sum_i \mu_i+\sum_t \varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0
The following observation will be crucial and used multiple times.
Observation 5.4. If ∑ i μ i + ∑ t ε t = 0 \sum_i \mu_i+\sum_t \varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0 and v v v is a vertex such that at least x x x vertices in V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1} \cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) are not outneighbors of v v v , then v v v has at least x x x outneighbors outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1} \cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) , each with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . In particular, every vertex v ∈ T v \in T v ∈ T satisfying 1 ∈ R v 1 \in R_v 1 ∈ R v has an outneighbor outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1} \cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 .
Proof. Since μ p ( v ) = 0 \mu_{p(v)}=0 μ p ( v ) = 0 ,
d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ , d^+(v) \ge\delta^+(G)=|V_{p(v)+1}|+|T_{p(v)}|, d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ ,
and so v v v has at least x x x outneighbors outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1} \cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) . Every such outneighbor in V ′ V' V ′ has a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 , as wanted. If there is an outneighbor u u u in T ∖ T p ( v ) T \setminus T_{p(v)} T ∖ T p ( v ) with position p ( v ) + 1 p(v)+1 p ( v ) + 1 , then, since ε u = 0 \varepsilon_u=0 ε u = 0 , V p ( v ) V_{p(v)} V p ( v ) is an in-pointing blob of u u u , contradicting the fact that u ∉ T p ( v ) u \notin T_{p(v)} u ∈ / T p ( v ) .
If v v v satisfies 1 ∈ R v 1 \in R_v 1 ∈ R v , then v v v is in T p ( v ) T_{p(v)} T p ( v ) , so not all vertices in T p ( v ) T_{p(v)} T p ( v ) are its outneighbors and v v v has an outneighbor with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 .
This allows us to solve all the cases with ∑ i μ i + ∑ t ε t = 0 \sum_i \mu_i+\sum_t \varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0 . Each of the cases below is illustrated in a figure. There, the blobs are labelled relative to the position of v v v , the thick gray arrows represent the arcs between consecutive blobs. An arrow from a blob to a vertex, or from a vertex to a blob, indicates that the vertex has at least 2 k 2k 2 k inneighbors, respectively outneighbors, in this blob. All the drawn arrows are forced by the arguments, and the highlighted paths are the detours and sidewalks leading to a contradiction.
Case ( k , ℓ m o d k ) = ( 4 , 2 ) (k,\ell\bmod k)=(4,2) ( k , ℓ mod k ) = ( 4 , 2 ) : Let v ∈ T v \in T v ∈ T be a vertex with 1 ∈ R v 1 \in R_v 1 ∈ R v . By Observation 5.4, v v v has an outneighbor w w w outside T p ( v ) T_{p(v)} T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . To avoid having a detour of remainder 2 2 2 mod 4 4 4 , the position of w w w must be also different than p ( v ) p(v) p ( v ) and p ( v ) − 1 p(v)-1 p ( v ) − 1 , so p ( w ) = p ( v ) − 2 p(w)=p(v)-2 p ( w ) = p ( v ) − 2 . This means that v v v and w w w creates a detour of remainder 3 3 3 mod 4 4 4 (see Figure 2 ). To avoid contradiction with Observation 4.21, the sidewalk of remainder 3 3 3 must have a center v v v or w w w . In the former, V p ( v ) − 2 V_{p(v)-2} V p ( v ) − 2 is an in-pointing blob of v v v , which creates with w w w a forbidden detour of remainder 2 2 2 mod 4 4 4 . While in the latter, V p ( v ) V_{p(v)} V p ( v ) is an in-pointing blob of w w w , so w ∈ T p ( v ) w \in T_{p(v)} w ∈ T p ( v ) , contradicting the definition of w w w .
Figure 2. Case ( k , ℓ m o d k ) = ( 4 , 2 ) (k,\ell\bmod k)=(4,2) ( k , ℓ mod k ) = ( 4 , 2 ) .
Case ( k , ℓ m o d k ) = ( 4 , 3 ) (k,\ell\bmod k)=(4,3) ( k , ℓ mod k ) = ( 4 , 3 ) with ∑ i μ i + ∑ t ε t = 0 \sum_i \mu_i+\sum_t \varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0 : Similarly as in the previous case, let v ∈ T v \in T v ∈ T be a vertex with $1 \in R_v$. By Observation 5.4, v v v has an outneighbor w w w outside T p ( v ) T_{p(v)} T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . To avoid having a detour of remainder 3 3 3 mod 4 4 4 , the position of w w w must be also different than $p(v)-1婷婷五月 and p ( v ) − 2 p(v)-2 p ( v ) − 2 , so p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) . Applying again Observation 5.4 , but for vertex w w w , for which v ∈ T p ( v ) v \in T_{p(v)} v ∈ T p ( v ) is not an outneighbor, we obtain an outneighbor u u u of w w w outside T p ( v ) T_{p(v)} T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . Independently of the position of u u u , there is a detour of remainder 3 mod 4 (see Figure 3 ).
Figure 3. Case ( k , ℓ m o d k ) = ( 4 , 3 ) (k,\ell\bmod k)=(4,3) ( k , ℓ mod k ) = ( 4 , 3 ) with ∑ i μ i + ∑ t ε t = 0 \sum_i\mu_i+\sum_t\varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0 and all possible positions of u u u .
Case ( k , ℓ m o d k ) = ( 5 , 3 ) (k,\ell\bmod k)=(5,3) ( k , ℓ mod k ) = ( 5 , 3 ) with ∑ i μ i + ∑ t ε t = 0 \sum_i\mu_i+\sum_t\varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0 :
Let v ∈ T v \in T v ∈ T be a vertex with 1 ∈ R v 1 \in R_v 1 ∈ R v . By Observation 5.4 , v v v has an outneighbor w w w outside T p ( v ) T_{p(v)} T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . To avoid having a detour of remainder 3 mod 5, the position of w w w must be also different than p ( v ) − 1 p(v)-1 p ( v ) − 1 and p ( v ) − 2 p(v)-2 p ( v ) − 2 , so p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) or p ( w ) = p ( v ) + 2 p(w)=p(v)+2 p ( w ) = p ( v ) + 2 . We consider those two options separately. Also distinguishing between the case of family ( { 1 } , { 1 } ) (\{1\},\{1\}) ({ 1 } , { 1 }) and all the other families. Note that other families always include a sidewalk of remainder 4.
Consider first all the families except ( { 1 } , { 1 } ) (\{1\},\{1\}) ({ 1 } , { 1 }) . If p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) , then we apply Observation 5.4 for vertex w w w , for which v v v is not an outneighbor, and obtain a vertex u u u outside T p ( v ) T_{p(v)} T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . The only option avoiding a detour of remainder 3 mod 5 is to have p ( u ) = p ( v ) + 2 p(u)=p(v)+2 p ( u ) = p ( v ) + 2 . Then w w w and u u u create a detour of remainder 4 mod 5 (see Figure 4 (a)). By Observation 4.21 , we can combine it with a sidewalk of remainder 4, unless 4 ∈ R w 4 \in R_w 4 ∈ R w or 4 ∈ R u 4 \in R_u 4 ∈ R u . In the former w w w and u u u create a detour of remainder 3 mod 5, while in the latter u ∈ T p ( v ) u \in T_{p(v)} u ∈ T p ( v ) contradicting its definition. If p ( w ) = p ( v ) + 2 p(w)=p(v)+2 p ( w ) = p ( v ) + 2 , then v v v and w w w create a detour of remainder 4 mod 5 (see Figure 4 (b)). We can combine it with a sidewalk of remainder 4 mod 5, unless 4 ∈ R v 4 \in R_v 4 ∈ R v or 4 ∈ R w 4 \in R_w 4 ∈ R w . Similarly as earlier, in the former v v v and w w w create a detour of remainder 3 mod 5, while in the latter w ∈ T p ( v ) w \in T_{p(v)} w ∈ T p ( v ) contradicting its definition.
Figure 4. Case ( k , ℓ m o d k ) = ( 5 , 3 ) (k,\ell\bmod k)=(5,3) ( k , ℓ mod k ) = ( 5 , 3 ) with ∑ i μ i + ∑ t ε t = 0 \sum_i\mu_i+\sum_t\varepsilon_t=0 ∑ i μ i + ∑ t ε t = 0 : (a), (b) for the families containing a sidewalk of remainder 4; (c), (d) for the family ( { 1 } , { 1 } ) (\{1\},\{1\}) ({ 1 } , { 1 }) with p ( w ) = p ( v ) + 2 p(w)=p(v)+2 p ( w ) = p ( v ) + 2 and p ( w ′ ) = p ( v ′ ) + 2 p(w')=p(v')+2 p ( w ′ ) = p ( v ′ ) + 2 .
Therefore, consider now the family ( { 1 } , { 1 } ) (\{1\},\{1\}) ({ 1 } , { 1 }) . If p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) , then v v v and w w w create a detour of remainder 2. We can combine it with the second center of a sidewalk of remainder 1, unless 1 ∈ R w 1 \in R_w 1 ∈ R w . But then p ( v ) p(v) p ( v ) is an in-pointing blob of w w w , so w ∈ T p ( v ) w \in T_{p(v)} w ∈ T p ( v ) contradicting its definition. Thus, p ( w ) = p ( v ) + 2 p(w)=p(v)+2 p ( w ) = p ( v ) + 2 and v v v and w w w create a detour of remainder 4 mod 5. We can use the same reasoning for the second vertex v ′ v' v ′ satisfying 1 ∈ R v ′ 1\in R_{v'} 1 ∈ R v ′ to obtain vertex w ′ w' w ′ with p ( w ′ ) = p ( v ′ ) + 2 p(w')=p(v')+2 p ( w ′ ) = p ( v ′ ) + 2 creating a detour of remainder 4 mod 5. If { v , w } ∩ { v ′ , w ′ } = ∅ \{v,w\}\cap\{v',w'\}=\varnothing { v , w } ∩ { v ′ , w ′ } = ∅ , then, choosing the added vertices distinct, we obtain two vertex-disjoint detours of remainder 4, which can be combined using Observation 4.17 into a C → ℓ \overrightarrow{C}_{\ell} C ℓ . If v ′ = w v'=w v ′ = w , then v v v , w w w and w ′ w' w ′ create a detour of remainder 3 mod 5 (see Figure 4 (c)), and symmetrically if w ′ = v w'=v w ′ = v . While if w ′ = w w'=w w ′ = w , then p ( v ) = p ( v ′ ) p(v)=p(v') p ( v ) = p ( v ′ ) , and one of the arcs v v ′ vv' v v ′ and v ′ v v'v v ′ v is missing, say v ′ v' v ′ is not an outneighbor of v v v . Since v , v ′ ∈ T p ( v ) v,v'\in T_{p(v)} v , v ′ ∈ T p ( v ) , by Observation 5.4 , v v v has an outneighbor u u u distinct from w w w outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1}\cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . As for w w w , we get p ( u ) = p ( v ) + 2 p(u)=p(v)+2 p ( u ) = p ( v ) + 2 , so v v v and u u u create a detour of remainder 4. Since u ≠ v ′ u\ne v' u = v ′ and w ≠ v w\ne v w = v , the pairs { v , u } \{v,u\} { v , u } and { v ′ , w } \{v',w\} { v ′ , w } are disjoint, which leads to a contradiction as before (see Figure 4 (d)).
Case ( k , ℓ m o d k ) = ( 5 , 4 ) (k,\ell\bmod k)=(5,4) ( k , ℓ mod k ) = ( 5 , 4 ) : Among all the three vertices t ∈ T t\in T t ∈ T with 1 ∈ R t 1\in R_t 1 ∈ R t , let v v v be such that p ( v ) − 1 p(v)-1 p ( v ) − 1 is different than the position of the other two vertices. Similarly as in the previous cases, by Observation 5.4 , v v v has an outneighbor w w w outside T p ( v ) T_{p(v)} T p ( v ) with a position different than p ( v ) + 1 p(v)+1 p ( v ) + 1 . To avoid having a detour of remainder 4 mod 5, the position of w w w must be also different than p ( v ) − 2 p(v)-2 p ( v ) − 2 and p ( v ) + 2 p(v)+2 p ( v ) + 2 , so p ( w ) = p ( v ) − 1 p(w)=p(v)-1 p ( w ) = p ( v ) − 1 or p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) (see Figure 5 ). If p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) , then v v v and w w w create a detour of remainder 2 that can be combined by Observation 4.21 with the sidewalks of remainder 1 using other two vertices in T T T , unless 1 ∈ R w 1\in R_w 1 ∈ R w . But this implies that w ∈ T p ( v ) w\in T_{p(v)} w ∈ T p ( v ) contradicting its definition. If p ( w ) = p ( v ) − 1 p(w)=p(v)-1 p ( w ) = p ( v ) − 1 , then also v v v and w w w create a detour of remainder 2 and, by the assumption on v v v , the two other vertices in T T T creating sidewalks of remainder 1 mod 5 are distinct from w w w . Thus, the detour can be combined with the two sidewalks and we obtain a contradiction.
Figure 5. Case ( k , ℓ m o d k ) = ( 5 , 4 ) (k,\ell\bmod k)=(5,4) ( k , ℓ mod k ) = ( 5 , 4 ) with the two possible positions of w w w .
Finalization in the cases with ∑ i μ i + ∑ t ϵ t = 1 \sum_i \mu_i+\sum_t\epsilon_t=1 ∑ i μ i + ∑ t ϵ t = 1
Note that ∑ i = 1 k μ i + ∑ t ∈ T ϵ t = 1 \sum_{i=1}^{k}\mu_i+\sum_{t\in T}\epsilon_t=1 ∑ i = 1 k μ i + ∑ t ∈ T ϵ t = 1 implies that ∑ t ∈ T ∣ R t ∣ = k − 2 \sum_{t\in T}|R_t|=k-2 ∑ t ∈ T ∣ R t ∣ = k − 2 and ℓ m o d k = 3 \ell\bmod k=3 ℓ mod k = 3 , and the family of non-empty sets R t R_t R t is one of the six families listed in Table 3 . Intuitively, the sets of remainders are saturated, and any additional remainder leads to a contradiction.
If ∑ i = 1 k μ i = 1 \sum_{i=1}^{k}\mu_i=1 ∑ i = 1 k μ i = 1 , then not every vertex t ∈ T t\in T t ∈ T having 1 ∈ R t 1\in R_t 1 ∈ R t needs to have an outneighbor not following the cycle structure, so the conclusion of Observation 5.4 does not hold. The following two observations will allow us to control the irregular blobs and vertices, and play the role of Observation 5.4 .
Observation 5.5. If ∑ i μ i + ∑ t ϵ t = 1 \sum_i\mu_i+\sum_t\epsilon_t=1 ∑ i μ i + ∑ t ϵ t = 1 and a vertex v v v satisfies 1 ∈ R v 1\in R_v 1 ∈ R v and ϵ v = 0 \epsilon_v=0 ϵ v = 0 , then every outneighbor u u u of v v v outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1}\cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) satisfies u ∈ T u\in T u ∈ T , ϵ u = 1 \epsilon_u=1 ϵ u = 1 and O u = { p ( v ) + 2 } O_u=\{p(v)+2\} O u = { p ( v ) + 2 } .
Proof. By Observation 5.3, O v = { p ( v ) + 1 } O_v=\{p(v)+1\} O v = { p ( v ) + 1 } , so all outneighbors of v v v in V ′ ∖ V p ( v ) + 1 V'\setminus V_{p(v)+1} V ′ ∖ V p ( v ) + 1 lie in X X X . Hence, u ∈ X ∩ V j u\in X\cap V_j u ∈ X ∩ V j for some j ≠ p ( v ) + 1 j\ne p(v)+1 j = p ( v ) + 1 , or u ∈ T ∖ T p ( v ) u\in T\setminus T_{p(v)} u ∈ T ∖ T p ( v ) .
In the former case, u ∈ X ∩ V j u\in X\cap V_j u ∈ X ∩ V j for some j ≠ p ( v ) + 1 j\ne p(v)+1 j = p ( v ) + 1 , and for each i ∈ I v i\in I_v i ∈ I v there is a detour from V i V_i V i through v v v to u u u of remainder i − j + 2 i-j+2 i − j + 2 . If such a remainder is not in R v ∪ { 0 } R_v\cup\{0\} R v ∪ { 0 } , then we get a contradiction by Observation 4.21 . Therefore, all the ∣ I v ∣ |I_v| ∣ I v ∣ remainders i − j + 2 i-j+2 i − j + 2 are in R v ∪ { 0 } R_v\cup\{0\} R v ∪ { 0 } . Since ϵ v = 0 \epsilon_v=0 ϵ v = 0 , we have ∣ R v ∣ + 1 = ∣ I v ∣ |R_v|+1=|I_v| ∣ R v ∣ + 1 = ∣ I v ∣ , so I v − j + 2 = R v ∪ { 0 } I_v-j+2=R_v\cup\{0\} I v − j + 2 = R v ∪ { 0 } . But also I v − ( p ( v ) + 1 ) + 2 = R v ∪ { 0 } I_v-(p(v)+1)+2=R_v\cup\{0\} I v − ( p ( v ) + 1 ) + 2 = R v ∪ { 0 } , so R v ∪ { 0 } R_v\cup\{0\} R v ∪ { 0 } is invariant under the translation by p ( v ) + 1 − j ≠ 0 p(v)+1-j\ne0 p ( v ) + 1 − j = 0 , which is impossible, as in the proof of Observation 5.3. Therefore, u ∈ T ∖ T p ( v ) u\in T\setminus T_{p(v)} u ∈ T ∖ T p ( v ) . In particular, p ( v ) ∉ I u p(v)\notin I_u p ( v ) ∈ / I u .
Let j ∈ O u j\in O_u j ∈ O u . Since ϵ v = 0 \epsilon_v=0 ϵ v = 0 , for every r ∈ R v ∪ { 0 } r\in R_v\cup\{0\} r ∈ R v ∪ { 0 } there is a detour from V r + p ( v ) − 1 V_{r+p(v)-1} V r + p ( v ) − 1 through v u vu v u to V j V_j V j of remainder r + p ( v ) − j + 2 r+p(v)-j+2 r + p ( v ) − j + 2 . We claim that p ( v ) − j + 2 ∈ R u ∪ { 0 } p(v)-j+2\in R_u\cup\{0\} p ( v ) − j + 2 ∈ R u ∪ { 0 } . Otherwise, p ( v ) − j + 2 ≠ 0 p(v)-j+2\ne0 p ( v ) − j + 2 = 0 , and the detours for r = 0 r=0 r = 0 and r = 1 r=1 r = 1 have the consecutive remainders p ( v ) − j + 2 p(v)-j+2 p ( v ) − j + 2 and p ( v ) − j + 3 p(v)-j+3 p ( v ) − j + 3 , none of which is 3 by Observation 4.21 . Hence, p ( v ) − j + 2 = 1 p(v)-j+2=1 p ( v ) − j + 2 = 1 , or k = 5 k=5 k = 5 and p ( v ) − j + 2 = 4 p(v)-j+2=4 p ( v ) − j + 2 = 4 . In the former case, 1 ∉ R u 1\notin R_u 1 ∈ / R u and the detour for r = 1 r=1 r = 1 has remainder 2. If 2 ∈ R v 2\in R_v 2 ∈ R v , then the detour for r = 2 r=2 r = 2 has remainder 3. Otherwise, there is another vertex v ′ v' v ′ with 1 ∈ R v ′ 1\in R_{v'} 1 ∈ R v ′ , distinct from u u u as 1 ∉ R u 1\notin R_u 1 ∈ / R u , and we combine the detour with a sidewalk of remainder 1 centred at v ′ v' v ′ . In the latter case, 4 ∉ R u 4\notin R_u 4 ∈ / R u and the detour for r = 0 r=0 r = 0 has remainder 4. If 4 ∈ R v 4\in R_v 4 ∈ R v , then the detour for r = 4 r=4 r = 4 has remainder 3. Otherwise, the vertex with remainder 4 is distinct from v v v and u u u , and we combine the detour with a sidewalk of remainder 4 centred at it. In each case Observation 4.21 gives a contradiction, which proves the claim that p ( v ) − j + 2 ∈ R u ∪ { 0 } p(v)-j+2\in R_u\cup\{0\} p ( v ) − j + 2 ∈ R u ∪ { 0 } . Since also i − j + 2 ∈ R u ∪ { 0 } i-j+2 \in R_u \cup\{0\} i − j + 2 ∈ R u ∪ { 0 } for every i ∈ I u i \in I_u i ∈ I u , and p ( v ) ∉ I u p(v) \notin I_u p ( v ) ∈ / I u , the ∣ I u ∣ + 1 |I_u|+1 ∣ I u ∣ + 1 distinct values i − j + 2 i-j+2 i − j + 2 with i ∈ I u ∪ { p ( v ) } i \in I_u \cup\{p(v)\} i ∈ I u ∪ { p ( v )} lie in R u ∪ { 0 } R_u \cup\{0\} R u ∪ { 0 } . Thus, ∣ I u ∣ ≤ ∣ R u ∣ |I_u| \le|R_u| ∣ I u ∣ ≤ ∣ R u ∣ , so ε u = 1 \varepsilon_u=1 ε u = 1 and ( I u ∪ { p ( v ) } ) − j + 2 = R u ∪ { 0 } (I_u \cup\{p(v)\})-j+2=R_u \cup\{0\} ( I u ∪ { p ( v )}) − j + 2 = R u ∪ { 0 } . As this holds for every j ∈ O u j \in O_u j ∈ O u and R u ∪ { 0 } R_u \cup\{0\} R u ∪ { 0 } is not invariant under a non-zero translation, O u = { j } O_u=\{j\} O u = { j } . Then R u = ( I u − j + 2 ) ∖ { 0 } R_u=(I_u-j+2)\setminus\{0\} R u = ( I u − j + 2 ) ∖ { 0 } has ∣ I u ∣ |I_u| ∣ I u ∣ elements, so I u − j + 2 = R u I_u-j+2=R_u I u − j + 2 = R u . Hence, p ( v ) − j + 2 = 0 p(v)-j+2=0 p ( v ) − j + 2 = 0 , that is, O u = { p ( v ) + 2 } O_u=\{p(v)+2\} O u = { p ( v ) + 2 } .
Observation 5.6. If ∑ i μ i + ∑ t ε t = 1 \sum_i \mu_i+\sum_t\varepsilon_t=1 ∑ i μ i + ∑ t ε t = 1 and a vertex v v v satisfies 1 ∈ R v 1\in R_v 1 ∈ R v and ε v = 0 \varepsilon_v=0 ε v = 0 , then μ p ( v ) = 1 \mu_{p(v)}=1 μ p ( v ) = 1 or v v v has an outneighbor u u u in T ∖ T p ( v ) T\setminus T_{p(v)} T ∖ T p ( v ) that satisfies ε u = 1 \varepsilon_u=1 ε u = 1 and O u = { p ( v ) + 2 } O_u=\{p(v)+2\} O u = { p ( v ) + 2 } .
Proof. The assumptions ε v = 0 \varepsilon_v=0 ε v = 0 and 1 ∈ R v 1\in R_v 1 ∈ R v imply that v ∈ T p ( v ) v\in T_{p(v)} v ∈ T p ( v ) , so by
d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { v } ∣ + 1 − μ p ( v ) , d^+(v)\ge\delta^+(G)=|V_{p(v)+1}|+|T_{p(v)}|-\mu_{p(v)}=|V_{p(v)+1}|+|T_{p(v)}\setminus\{v\}|+1-\mu_{p(v)}, d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { v } ∣ + 1 − μ p ( v ) ,
either μ p ( v ) = 1 \mu_{p(v)}=1 μ p ( v ) = 1 or v v v has an outneighbor u u u outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1}\cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) . In the latter, by Observation 5.5 , u ∈ T ∖ T p ( v ) u\in T\setminus T_{p(v)} u ∈ T ∖ T p ( v ) , ε u = 1 \varepsilon_u=1 ε u = 1 and O u = { p ( v ) + 2 } O_u=\{p(v)+2\} O u = { p ( v ) + 2 } .
We are ready to finalize the proof in the remaining cases.
Cases with ∑ i μ i = 1 \sum_i\mu_i=1 ∑ i μ i = 1 :
Since ∑ i μ i = 1 \sum_i\mu_i=1 ∑ i μ i = 1 , we have ∑ t ∈ T ε t = 0 \sum_{t\in T}\varepsilon_t=0 ∑ t ∈ T ε t = 0 . All the considered families contain a vertex v v v with { 1 , 2 } ⊆ R v \{1,2\}\subseteq R_v { 1 , 2 } ⊆ R v or two vertices u , v u,v u , v with 1 ∈ R u ∩ R v 1\in R_u\cap R_v 1 ∈ R u ∩ R v . In the former, Observation 5.6 gives μ p ( v ) = 1 \mu_{p(v)}=1 μ p ( v ) = 1 , while by Observation 5.2, μ p ( v ) + 1 = 1 \mu_{p(v)+1}=1 μ p ( v ) + 1 = 1 , which gives a contradiction with (2). In the latter, by Observation 5.6 , μ p ( v ) = μ p ( u ) = 1 \mu_{p(v)}=\mu_{p(u)}=1 μ p ( v ) = μ p ( u ) = 1 , so p ( u ) = p ( v ) p(u)=p(v) p ( u ) = p ( v ) . Among vertices v v v and u u u , there is at least one that does not have an arc to the other vertex. We may assume it is v v v . Since u , v ∈ T p ( v ) u,v\in T_{p(v)} u , v ∈ T p ( v ) ,
d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { u , v } ∣ + 1 , d^+(v)\ge\delta^+(G)=|V_{p(v)+1}|+|T_{p(v)}|-\mu_{p(v)}=|V_{p(v)+1}|+|T_{p(v)}\setminus\{u,v\}|+1, d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { u , v } ∣ + 1 ,
so v v v has an outneighbor w w w outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1}\cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) . By Observation 5.5 , ε w = 1 \varepsilon_w=1 ε w = 1 , which is a contradiction.
Cases with ∑ t ε t = 1 \sum_t\varepsilon_t=1 ∑ t ε t = 1 :
Let z ∈ T z\in T z ∈ T be the vertex with ε z = 1 \varepsilon_z=1 ε z = 1 . The assumption ∑ t ε t = 1 \sum_t\varepsilon_t=1 ∑ t ε t = 1 gives ∑ i μ i = 0 \sum_i\mu_i=0 ∑ i μ i = 0 , so no set R t R_t R t contains 2 by Observation 5.2. Thus, there are two vertices u , v ∈ T u,v\in T u , v ∈ T with 1 ∈ R u ∩ R v 1\in R_u\cap R_v 1 ∈ R u ∩ R v .
Assume first that both u u u and v v v are distinct from z z z . Then ε v = ε u = 0 \varepsilon_v=\varepsilon_u=0 ε v = ε u = 0 and by Observation 5.6 , v z , u z ∈ E ( G ) vz,uz\in E(G) v z , u z ∈ E ( G ) and O z = { p ( v ) + 2 } = { p ( u ) + 2 } O_z=\{p(v)+2\}=\{p(u)+2\} O z = { p ( v ) + 2 } = { p ( u ) + 2 } , so p ( v ) = p ( u ) p(v)=p(u) p ( v ) = p ( u ) . As before, we may assume that v v v has no arc to u u u , and since
d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { u , v } ∣ + 2 , d^+(v)\ge\delta^+(G)=|V_{p(v)+1}|+|T_{p(v)}|-\mu_{p(v)}=|V_{p(v)+1}|+|T_{p(v)}\setminus\{u,v\}|+2, d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { u , v } ∣ + 2 ,
vertex v v v has at least two outneighbors outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1}\cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) . The one distinct from z z z gives a contradiction by Observation 5.5 .
Therefore, z z z is one of the vertices u u u and v v v , by symmetry, we may assume that v = z v=z v = z . By Observations 5.6 and 5.5 , u v ∈ E ( G ) uv\in E(G) uv ∈ E ( G ) and O v = { p ( u ) + 2 } O_v=\{p(u)+2\} O v = { p ( u ) + 2 } , so p ( v ) = p ( u ) + 1 p(v)=p(u)+1 p ( v ) = p ( u ) + 1 . Since v ∈ T p ( v ) v\in T_{p(v)} v ∈ T p ( v ) as 1 ∈ R v 1\in R_v 1 ∈ R v , by
d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { v } ∣ + 1 , d^+(v)\ge\delta^+(G)=|V_{p(v)+1}|+|T_{p(v)}|-\mu_{p(v)}=|V_{p(v)+1}|+|T_{p(v)}\setminus\{v\}|+1, d + ( v ) ≥ δ + ( G ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∣ − μ p ( v ) = ∣ V p ( v ) + 1 ∣ + ∣ T p ( v ) ∖ { v } ∣ + 1 ,
v v v has an outneighbor w w w outside V p ( v ) + 1 ∪ T p ( v ) V_{p(v)+1}\cup T_{p(v)} V p ( v ) + 1 ∪ T p ( v ) , so with p ( w ) ≠ p ( v ) + 1 p(w)\ne p(v)+1 p ( w ) = p ( v ) + 1 . The possible positions of w w w are shown in Figure 6 . If p ( w ) = p ( v ) p(w)=p(v) p ( w ) = p ( v ) , then v v v and w w w create a detour of remainder 2 that can be combined with a sidewalk of remainder 1 centered at u u u , leading to a contradiction by Observation 4.21 . While if p ( w ) = p ( v ) − 1 p(w)=p(v)-1 p ( w ) = p ( v ) − 1 or p ( w ) = p ( v ) − 2 p(w)=p(v)-2 p ( w ) = p ( v ) − 2 , then u u u , v v v and w w w create a forbidden detour of remainder 3. This already gives a contradiction in the case k = 4 k = 4 k = 4 , while for k = 5 k = 5 k = 5 we have p ( w ) = p ( v ) + 2 p(w) = p(v) + 2 p ( w ) = p ( v ) + 2 and u u u , v v v , w w w create a detour of remainder 4. To avoid contradiction by Observation 4.21 , in case of the family ( { 1 } , { 1 } , { 4 } ) \left(\{1\}, \{1\}, \{4\}\right) ( { 1 } , { 1 } , { 4 } ) , we have 4 ∈ R w 4 \in R_w 4 ∈ R w , which implies that w ∈ T p ( v ) w \in T_{p(v)} w ∈ T p ( v ) , a contradiction. Whereas, in case of the family ( { 1 } , { 1 , 4 } ) \left(\{1\}, \{1, 4\}\right) ( { 1 } , { 1 , 4 } ) , we must have 4 ∈ R u 4 \in R_u 4 ∈ R u or 4 ∈ R v 4 \in R_v 4 ∈ R v . Then u u u , v v v , w w w create a forbidden detour of remainder 3, a contradiction.
Figure 6. Cases with ∑ t ε t = 1 \sum_t \varepsilon_t = 1 ∑ t ε t = 1 , drawn for k = 5 k = 5 k = 5 , with all possible positions of w w w .
AI statement
All results in this paper have been obtained without AI assistance. The paper itself, except Figure 2 –6, has also been written fully by the authors. The authors have used Claude Opus 5.5 only for linguistic checks, a final correctness check and making figures.