2020 Mathematics Subject Classification. 05C20, 05C38, 05C45.
Introduction
Cycles in tournaments have been widely studied. Camion [3 ] proved that every strongly connected tournament has a Hamilton cycle. Moon [11 ] established a more general result, showing that every strongly connected tournament on n n n vertices is vertex-pancyclic, meaning that every vertex lies on a cycle of each length from 3 to n n n .
A c c c -partite tournament is an orientation of a complete c c c -partite graph. For a vertex v v v , let d + ( v ) d^{+}(v) d + ( v ) and d − ( v ) d^{-}(v) d − ( v ) denote its outdegree and indegree, respectively. A c c c -partite tournament is d d d -regular if d + ( v ) = d − ( v ) = d d^{+}(v) = d^{-}(v) = d d + ( v ) = d − ( v ) = d for every vertex v v v . In this case, all partite classes have the same size r r r , and d = ( c − 1 ) r / 2 d = (c - 1)r/2 d = ( c − 1 ) r /2 . A natural question is whether similar pancyclicity results hold for regular c c c -partite tournaments. Yeo [23 ] proved that every regular c c c -partite tournament is vertex-pancyclic when c ≥ 5 c \ge5 c ≥ 5 . However, this fails for c = 3 c = 3 c = 3 . Indeed, consider the regular 3-partite tournament with all edges directed from V i V_i V i to V i + 1 V_{i+1} V i + 1 , where indices are taken modulo 3. Every cycle in this regular 3-partite tournament has length divisible by three. This motivates studying the existence of cycles of all lengths divisible by three. Bondy [2 ] , Yeo [21 ] and Volkmann [16 ] established the existence of cycles of lengths 3, 3 r 3r 3 r and 3 r − 3 3r - 3 3 r − 3 , respectively, in regular tripartite tournaments. Volkmann [17 ] further proved the existence of a 6-cycle and proposed the following conjecture.
Conjecture 1.1 (Volkmann [17 ] ). Every regular tripartite tournament with r r r vertices in each class contains a cycle of length 3 k 3k 3 k for every 1 ≤ k ≤ r 1 \le k \le r 1 ≤ k ≤ r .
Stella and Volkmann [13 ] proved the case k = 3 k = 3 k = 3 later. A path or cycle is k k k -balanced if it contains exactly k k k vertices from each partite class, and simply balanced if k = 1 k = 1 k = 1 . Volkmann and Winzen [19 ] proved that every regular c c c -partite tournament with c ≥ 5 c \ge5 c ≥ 5 contains an ( r − 1 ) (r - 1) ( r − 1 ) -balanced cycle. More generally, they showed that, for every fixed positive integer s s s , such a tournament contains an ( r − s ) (r - s) ( r − s ) -balanced cycle whenever r r r is sufficiently large. They further conjectured the following.
Conjecture 1.2 (Volkmann and Winzen [19 ] ). Every regular c c c -partite tournament with c ≥ 5 c \ge5 c ≥ 5 and common partite size r r r contains a k k k -balanced cycle for every 1 ≤ k ≤ r 1 \le k \le r 1 ≤ k ≤ r .
The case k = 1 k = 1 k = 1 was later settled in [20 ] . The condition c ≥ 5 c \ge5 c ≥ 5 is necessary, as Volkmann constructed a family of regular four-partite tournaments containing no balanced cycle [20 ] . This motivated Volkmann and Winzen [18 ] to propose the following weaker conjecture for balanced paths.
Conjecture 1.3 (Volkmann and Winzen [18 ] ). Every regular c c c -partite tournament with c ≥ 2 c \ge2 c ≥ 2 and common partite size r r r contains a k k k -balanced path for every 1 ≤ k ≤ r 1 \le k \le r 1 ≤ k ≤ r .
The conjecture is known to hold for c = 2 c = 2 c = 2 , and the cases k ∈ { 1 , 2 , r − 1 , r } k \in\{1, 2, r - 1, r\} k ∈ { 1 , 2 , r − 1 , r } have been established for all c ≥ 2 c \ge2 c ≥ 2 in [18 ] . Our first result confirms Conjectures 1.1 to 1.3 for all r ≥ r 0 r \ge r_0 r ≥ r 0 , where r 0 r_0 r 0 is an absolute constant.
Theorem 1.4. There exists a positive integer r 0 r_0 r 0 such that for every c ≥ 3 c \ge3 c ≥ 3 and r ≥ r 0 r \ge r_0 r ≥ r 0 , every regular c c c -partite tournament with common partite size r r r contains a k k k -balanced cycle for every $1 \le k \le r$ if c = 3 c = 3 c = 3 or c ≥ 5 c \ge5 c ≥ 5 , and for every 2 ≤ k ≤ r 2 \le k \le r 2 ≤ k ≤ r if $c = 4.
We also study ( p , q ) (p, q) ( p , q ) -cycle-factors in regular c c c -partite tournaments. A ( p , q ) (p, q) ( p , q ) -cycle-factor consists of two vertex-disjoint cycles of lengths p p p and q q q that together cover all vertices. Yeo [23 ] proposed the following conjecture.
Conjecture 1.5 (Yeo [23 ] ). Every regular c c c -partite tournament G G G with c ≥ 5 c \ge5 c ≥ 5 contains a ( p , ∣ V ( G ) ∣ − p ) (p, \lvert V(G) \rvert- p) ( p , ∣ V ( G )∣ − p ) -cycle-factor for every 3 ≤ p ≤ ∣ V ( G ) ∣ − 3 3 \le p \le\lvert V(G) \rvert- 3 3 ≤ p ≤ ∣ V ( G )∣ − 3 .
Bessy and Thiebaut [1 ] proposed a weaker conjecture under a stronger regularity condition.
Conjecture 1.6 (Bessy and Thiebaut [1 ] ). Every c c c -partite tournament G G G with c ≥ 5 c \ge5 c ≥ 5 , in which the bipartite tournament between any two partite classes is t t t -regular, contains a ( p , ∣ V ( G ) ∣ − p ) (p, \lvert V(G) \rvert- p) ( p , ∣ V ( G )∣ − p ) -cycle-factor for every even integer 4 ≤ p ≤ ∣ V ( G ) ∣ − 4 4 \le p \le\lvert V(G) \rvert- 4 4 ≤ p ≤ ∣ V ( G )∣ − 4 .
Clearly, Conjecture 1.5 implies Conjecture 1.6 . Volkmann [15 ] also investigated the four-partite case, particularly cycle-factors containing a 4-cycle. Our second main result confirms Yeo’s conjecture for sufficiently large tournaments and extends it to c = 4 c = 4 c = 4 .
Theorem 1.7. There exists a positive integer r 0 r_0 r 0 such that for every c ≥ 4 c \ge4 c ≥ 4 and r ≥ r 0 r \ge r_0 r ≥ r 0 , every regular c c c -partite tournament G G G with common partite size r r r contains a ( p , c r − p ) (p, cr - p) ( p , cr − p ) -cycle-factor for every 3 ≤ p ≤ c r − 3 3 \le p \le cr - 3 3 ≤ p ≤ cr − 3 .
Organization. In § 1 , we collect the preliminary results. In § 2 , we prove Theorem 1.4 for c ≥ 4 c \ge4 c ≥ 4 . In § 3 , we establish the tripartite case by applying the stability theorem Theorem 4.3 , with the robust outexpander and extremal cases handled in Lemmas 4.7 and 4.8 , respectively. Finally, in § 4 , we prove Theorem 1.7 .
Preliminaries
Notations
Let G G G be a digraph. For v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , let N G + ( v ) = { u : v u ∈ E ( G ) } N_G^{+}(v) = \{u : vu \in E(G)\} N G + ( v ) = { u : v u ∈ E ( G )} and N G − ( v ) = { u : u v ∈ E ( G ) } N_G^{-}(v) = \{u : uv \in E(G)\} N G − ( v ) = { u : uv ∈ E ( G )} be its out- and in-neighborhoods, respectively, and d G ± ( v ) = ∣ N G ± ( v ) ∣ d_G^{\pm}(v) = |N_G^{\pm}(v)| d G ± ( v ) = ∣ N G ± ( v ) ∣ . For B ⊆ V ( G ) B \subseteq V(G) B ⊆ V ( G ) , set d G + ( v , B ) = ∣ N G + ( v ) ∩ B ∣ d_G^{+}(v, B) = |N_G^{+}(v) \cap B| d G + ( v , B ) = ∣ N G + ( v ) ∩ B ∣ and d G ( v , B ) = d G + ( v , B ) + d G − ( v , B ) d_G(v, B) = d_G^{+}(v, B) + d_G^{-}(v, B) d G ( v , B ) = d G + ( v , B ) + d G − ( v , B ) . The total degree of v v v is d G ( v ) = d G + ( v ) + d G − ( v ) d_G(v) = d_G^{+}(v) + d_G^{-}(v) d G ( v ) = d G + ( v ) + d G − ( v ) , and the minimum total degree of G G G is δ ( G ) \delta(G) δ ( G ) . The minimum and maximum semidegrees are δ 0 ( G ) = min v ∈ V ( G ) min { d G + ( v ) , d G − ( v ) } \delta^{0}(G) = \min_{v \in V(G)} \min\{d_G^{+}(v), d_G^{-}(v)\} δ 0 ( G ) = min v ∈ V ( G ) min { d G + ( v ) , d G − ( v )} and Δ 0 ( G ) = max v ∈ V ( G ) max { d G + ( v ) , d G − ( v ) } \Delta^{0}(G) = \max_{v \in V(G)} \max\{d_G^{+}(v), d_G^{-}(v)\} Δ 0 ( G ) = max v ∈ V ( G ) max { d G + ( v ) , d G − ( v )} . A vertex v v v of a tournament T T T is a source if d T − ( v ) = 0 d_T^{-}(v) = 0 d T − ( v ) = 0 and a sink if d T + ( v ) = 0 d_T^{+}(v) = 0 d T + ( v ) = 0 .
For x , y ∈ V ( G ) x, y \in V(G) x , y ∈ V ( G ) , write x → y x \to y x → y (or x y xy x y ) if x y ∈ E ( G ) xy \in E(G) x y ∈ E ( G ) , and x → y → z x \to y \to z x → y → z if x y , y z ∈ E ( G ) xy, yz \in E(G) x y , y z ∈ E ( G ) . For disjoint sets A , B ⊆ V ( G ) A, B \subseteq V(G) A , B ⊆ V ( G ) , write A → B A \to B A → B if a → b a \to b a → b for all a ∈ A a \in A a ∈ A and b ∈ B b \in B b ∈ B . For any A , B ⊆ V ( G ) A, B \subseteq V(G) A , B ⊆ V ( G ) , let E G ( A , B ) = { x y ∈ E ( G ) : x ∈ A , y ∈ B } E_G(A, B) = \{xy \in E(G) : x \in A, y \in B\} E G ( A , B ) = { x y ∈ E ( G ) : x ∈ A , y ∈ B } , and e G ( A , B ) = ∣ E G ( A , B ) ∣ = ∑ v ∈ A d G + ( v , B ) e_G(A, B) = |E_G(A, B)| = \sum_{v \in A} d_G^{+}(v, B) e G ( A , B ) = ∣ E G ( A , B ) ∣ = ∑ v ∈ A d G + ( v , B ) . We omit the subscript G G G when clear. An ( A , B ) (A, B) ( A , B ) -path (resp. ( A , B ) (A, B) ( A , B ) -edge) is a path (resp. edge) from A A A to B B B . In particular, an ( a , b ) (a, b) ( a , b ) -path is a path from a a a to b b b .
A linear forest P = P 1 ∪ ⋯ ∪ P t P = P_1 \cup\cdots\cup P_t P = P 1 ∪ ⋯ ∪ P t consists of nontrivial vertex-disjoint paths, where each P i P_i P i is an ( a i , b i ) (a_i, b_i) ( a i , b i ) -path. Let V ˚ ( P ) \mathring{V}(P) V ˚ ( P ) be the set of its internal vertices. Then ∣ V ( P ) ∣ ≤ 2 e ( P ) |V(P)| \le2e(P) ∣ V ( P ) ∣ ≤ 2 e ( P ) . We write G ∘ P G \circ P G ∘ P for the digraph obtained by deleting V ˚ ( P ) \mathring{V}(P) V ˚ ( P ) , adding the edges a i b i a_i b_i a i b i for all i ∈ [ t ] i \in[t] i ∈ [ t ] , and retaining all other edges between the remaining vertices. These added edges form the auxiliary matching M P = { a i b i : i ∈ [ t ] } M_P = \{a_i b_i : i \in[t]\} M P = { a i b i : i ∈ [ t ]} .
For disjoint sets A , B A, B A , B , let M [ A , B ] M[A, B] M [ A , B ] denote a matching directed from A A A to B B B with ∣ M [ A , B ] ∣ = ∣ A ∣ = ∣ B ∣ |M[A, B]| = |A| = |B| ∣ M [ A , B ] ∣ = ∣ A ∣ = ∣ B ∣ .
A hypergraph H \mathcal{H} H consists of a vertex set V ( H ) V(\mathcal{H}) V ( H ) and an edge set E ( H ) ⊆ 2 V ( H ) E(\mathcal{H}) \subseteq2^{V(\mathcal{H})} E ( H ) ⊆ 2 V ( H ) . It is k k k -uniform if every edge has size k k k , and c c c -partite if its vertices can be partitioned into c c c classes, each meeting every edge in at most one vertex. The complete c c c -partite k k k -uniform hypergraph K ℓ 1 , … , ℓ c ( k ) K^{(k)}_{\ell_1,\ldots,\ell_c} K ℓ 1 , … , ℓ c ( k ) has vertex classes of sizes ℓ 1 , … , ℓ c \ell_1,\ldots,\ell_c ℓ 1 , … , ℓ c and contains all k k k -sets meeting each class in at most one vertex.
Throughout the paper, we omit all floor and ceiling functions whenever these are not crucial. The constants in the hierarchies used to state our results are chosen from right to left. For example, if we claim that a result holds whenever $0 < a \ll b \ll c \le 1$, then there are non-decreasing functions f , g : ( 0 , 1 ] → ( 0 , 1 ] f, g : (0, 1] \to(0, 1] f , g : ( 0 , 1 ] → ( 0 , 1 ] such that the result holds for all $0 < a, b, c \le 1$ with b ≤ f ( c ) b \le f(c) b ≤ f ( c ) and a ≤ g ( b ) a \le g(b) a ≤ g ( b ) .
Propositions in multipartite tournaments
We collect some basic properties and results on multipartite tournaments.
Proposition 2.1 (Rédei [12 ] ). Every tournament has a Hamilton path.
Proposition 2.2 (Camion [3 ] ). Every strongly connected tournament has a Hamilton cycle.
Proposition 2.3 (Yeo [23 ] ). Every regular c c c -partite tournament with c ≥ 5 c \ge5 c ≥ 5 is vertex-pancyclic.
Proposition 2.4 (Yeo [24 ] ). Every sufficiently large regular four-partite tournament is vertex-pancyclic.
Proposition 2.5 (Yeo [22 ] ). Let G G G be a c c c -partite tournament on n n n vertices whose partite sizes satisfy n 1 ≤ ⋯ ≤ n c n_1 \le\cdots\le n_c n 1 ≤ ⋯ ≤ n c . If Δ 0 ( G ) − δ 0 ( G ) ≤ ( n − n c − 1 − 2 n c + 2 ) / 2 \Delta^{0}(G) - \delta^{0}(G) \le(n - n_{c-1} - 2n_c + 2)/2 Δ 0 ( G ) − δ 0 ( G ) ≤ ( n − n c − 1 − 2 n c + 2 ) /2 , then G G G contains a Hamilton cycle.
Proposition 2.6 Let G G G be a regular c c c -partite tournament with partite classes V 1 , … , V c V_1, \ldots, V_c V 1 , … , V c , where c ≥ 2 c \ge2 c ≥ 2 . Then all partite classes have the same size r r r . Moreover, every vertex v ∈ V ( G ) v \in V(G) v ∈ V ( G ) satisfies d + ( v ) = d − ( v ) = ( c − 1 ) r / 2 d^{+}(v) = d^{-}(v) = (c - 1)r/2 d + ( v ) = d − ( v ) = ( c − 1 ) r /2 .
Regularity and embedding lemmas
For disjoint vertex sets X , Y X,Y X , Y in a graph G G G , write d G ( X , Y ) = e G ( X , Y ) / ( ∣ X ∣ ∣ Y ∣ ) d_G(X,Y)=e_G(X,Y)/(|X||Y|) d G ( X , Y ) = e G ( X , Y ) / ( ∣ X ∣∣ Y ∣ ) , where e G ( X , Y ) e_G(X,Y) e G ( X , Y ) denotes the number of edges between X X X and Y Y Y . The pair ( X , Y ) (X,Y) ( X , Y ) is ε \varepsilon ε -regular if ∣ d G ( X ′ , Y ′ ) − d G ( X , Y ) ∣ ≤ ε |d_G(X',Y')-d_G(X,Y)|\le\varepsilon ∣ d G ( X ′ , Y ′ ) − d G ( X , Y ) ∣ ≤ ε whenever X ′ ⊆ X X'\subseteq X X ′ ⊆ X , Y ′ ⊆ Y Y'\subseteq Y Y ′ ⊆ Y , ∣ X ′ ∣ ≥ ε ∣ X ∣ |X'|\ge\varepsilon|X| ∣ X ′ ∣ ≥ ε ∣ X ∣ and ∣ Y ′ ∣ ≥ ε ∣ Y ∣ |Y'|\ge\varepsilon|Y| ∣ Y ′ ∣ ≥ ε ∣ Y ∣ . It is ( ε , d ) (\varepsilon,d) ( ε , d ) -super-regular if it is ε \varepsilon ε -regular, has density at least d d d , and furthermore, d G ( a , Y ) > d ∣ Y ∣ d_G(a,Y)>d|Y| d G ( a , Y ) > d ∣ Y ∣ for all a ∈ X a\in X a ∈ X and d G ( b , X ) > d ∣ X ∣ d_G(b,X)>d|X| d G ( b , X ) > d ∣ X ∣ for all b ∈ Y b\in Y b ∈ Y .
Lemma 2.7 (Degree form of the Regularity Lemma). For every integer c ≥ 2 c\ge2 c ≥ 2 , ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and M ′ ∈ N M'\in\mathbb{N} M ′ ∈ N , there exist positive integers M = M ( ε , M ′ , c ) M=M(\varepsilon,M',c) M = M ( ε , M ′ , c ) and n 0 = n 0 ( ε , M ′ , c ) n_0=n_0(\varepsilon,M',c) n 0 = n 0 ( ε , M ′ , c ) such that the following holds. Let G G G be a c c c -partite graph with partite classes V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c of common size r r r , where n = c r ≥ n 0 n=cr\ge n_0 n = cr ≥ n 0 , and let d ∈ [ 0 , 1 ] d\in[0,1] d ∈ [ 0 , 1 ] . Then there exist an integer t t t with M ′ ≤ t ≤ M M'\le t\le M M ′ ≤ t ≤ M , a spanning subgraph G ′ ⊆ G G'\subseteq G G ′ ⊆ G , and a partition V ( G ) = V 0 ∪ ⋃ i = 1 c ⋃ j = 1 t V i j V(G)=V_0\cup\bigcup_{i=1}^{c}\bigcup_{j=1}^{t}V_{ij} V ( G ) = V 0 ∪ ⋃ i = 1 c ⋃ j = 1 t V ij , where V i j ⊆ V i V_{ij}\subseteq V_i V ij ⊆ V i , such that the following hold.
(i) ∣ V 0 ∩ V i ∣ ≤ ε r |V_0\cap V_i|\le\varepsilon r ∣ V 0 ∩ V i ∣ ≤ ε r for every 1 ≤ i ≤ c 1\le i\le c 1 ≤ i ≤ c .
(ii) All clusters V i j V_{ij} V ij have a common size m m m .
(iii) For every x ∈ V ( G ) x\in V(G) x ∈ V ( G ) , deg G ′ ( x ) > deg G ( x ) − ( d + ε ) n \deg_{G'}(x)>\deg_G(x)-(d+\varepsilon)n deg G ′ ( x ) > deg G ( x ) − ( d + ε ) n .
(iv) G ′ [ V i j ] G'[V_{ij}] G ′ [ V ij ] is empty for every 1 ≤ i ≤ c 1\le i\le c 1 ≤ i ≤ c and 1 ≤ j ≤ t 1\le j\le t 1 ≤ j ≤ t .
(v) For any two distinct clusters V i j V_{ij} V ij and V i ′ j ′ V_{i'j'} V i ′ j ′ , the bipartite graph G ′ [ V i j , V i ′ j ′ ] G'[V_{ij},V_{i'j'}] G ′ [ V ij , V i ′ j ′ ] is ε \varepsilon ε -regular and has density either 0 0 0 or at least d d d .
The reduced graph R R R has the clusters V i j V_{ij} V ij as its vertices, with two distinct clusters adjacent whenever G ′ G' G ′ contains an edge between them.
The following Blow-up Lemma was proved by Komlós, Sárközy and Szemerédi [8 ] .
Lemma 2.8 (Blow-up Lemma [8 ] ). For every d > 0 d>0 d > 0 and Δ ∈ N \Delta\in\mathbb{N} Δ ∈ N , there exists τ 0 = τ 0 ( d , Δ , F ) > 0 \tau_0=\tau_0(d,\Delta,F)>0 τ 0 = τ 0 ( d , Δ , F ) > 0 such that the following holds. Let F F F be any graph and let ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N . Let F ( ℓ ) F(\ell) F ( ℓ ) be the ℓ \ell ℓ -blow-up of F F F . Suppose that G 1 G_1 G 1 is a spanning subgraph of F ( ℓ ) F(\ell) F ( ℓ ) such that, for every x y ∈ E ( F ) xy\in E(F) x y ∈ E ( F ) , the pair G 1 [ V i , V j ] G_1[V_i,V_j] G 1 [ V i , V j ] is ( τ , d ) (\tau,d) ( τ , d ) -super-regular, where 0 < τ ≤ τ 0 0<\tau\le\tau_0 0 < τ ≤ τ 0 . Then G 1 G_1 G 1 contains a copy of every spanning subgraph H ⊆ F ( ℓ ) H\subseteq F(\ell) H ⊆ F ( ℓ ) with Δ ( H ) ≤ Δ \Delta(H)\le\Delta Δ ( H ) ≤ Δ , respecting the vertex classes.
Since our definition of super-regularity differs slightly from that in [9 ] , we make a minor adjustment to the parameters in the following lemma.
Lemma 2.9 (Kühn, Osthus and Taraz [9 ] ). Let G G G be a graph, and let G ′ G' G ′ and R R R be the pure graph and the reduced graph, respectively, obtained from the degree form of the Regularity Lemma with parameters ε \varepsilon ε and d d d . Suppose the nonexceptional clusters V 1 , … , V t V_1,\ldots,V_t V 1 , … , V t have common size m m m . Let H H H be a subgraph of R R R satisfying Δ ( H ) ≤ Δ \Delta(H)\le\Delta Δ ( H ) ≤ Δ , where Δ ε < 1 \Delta\varepsilon<1 Δ ε < 1 . Then there exist subsets V i ′ ⊆ V i V_i'\subseteq V_i V i ′ ⊆ V i for every V i ∈ V ( H ) V_i\in V(H) V i ∈ V ( H ) , each of size ( 1 − Δ ε ) m (1-\Delta\varepsilon)m ( 1 − Δ ε ) m , such that for every V i ′ V j ′ ∈ E ( H ) V_i'V_j'\in E(H) V i ′ V j ′ ∈ E ( H ) , the pair ( V i ′ , V j ′ ) (V_i',V_j') ( V i ′ , V j ′ ) in G ′ G' G ′ is ( 2 ε / ( 1 − Δ ε ) , d − ( Δ + 1 ) ε ) (2\varepsilon/(1-\Delta\varepsilon),d-(\Delta+1)\varepsilon) ( 2 ε / ( 1 − Δ ε ) , d − ( Δ + 1 ) ε ) -super-regular.
Lemma 2.10 (Erdős [5 ] ). For every c , k ∈ N c,k\in\mathbb{N} c , k ∈ N with c ≥ 2 c\ge2 c ≥ 2 and every α > 0 \alpha>0 α > 0 , there exists $r_0 such that the following holds. Let H H H be a c c c -partite c c c -uniform hypergraph with vertex classes V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c , each of size r ≥ r 0 r\ge r_0 r ≥ r 0 . If e ( H ) ≥ α r c e(H)\ge\alpha r^c e ( H ) ≥ α r c , then H H H contains a copy of K k , … , k ( c ) K^{(c)}_{k,\ldots,k} K k , … , k ( c ) .
Robust outexpanders
For an n n n -vertex digraph D D D , a set S ⊆ V ( D ) S\subseteq V(D) S ⊆ V ( D ) and ν > 0 \nu>0 ν > 0 , define R N ν , D + ( S ) : = { v ∈ V ( D ) : ∣ N D − ( v ) ∩ S ∣ ≥ ν n } RN^+_{\nu,D}(S):=\{v\in V(D):|N^-_D(v)\cap S|\ge\nu n\} R N ν , D + ( S ) := { v ∈ V ( D ) : ∣ N D − ( v ) ∩ S ∣ ≥ ν n } . The digraph is a robust ( ν , τ ) (\nu,\tau) ( ν , τ ) -outexpander if ∣ R N ν , D + ( S ) ∣ ≥ ∣ S ∣ + ν n |RN^+_{\nu,D}(S)|\ge|S|+\nu n ∣ R N ν , D + ( S ) ∣ ≥ ∣ S ∣ + ν n whenever τ n ≤ ∣ S ∣ ≤ ( 1 − τ ) n \tau n\le|S|\le(1-\tau)n τ n ≤ ∣ S ∣ ≤ ( 1 − τ ) n . We use the following results on outexpanders to prove the non-extremal case.
Lemma 2.11 (Girão, Granet, Kühn, Lo, and Osthus [6 ] ). Let 0 < 1 / n ≪ ξ ≪ ν ′ ≪ α , ν , τ ≪ 1 0 < 1/n \ll\xi\ll\nu' \ll\alpha,\nu,\tau\ll1 0 < 1/ n ≪ ξ ≪ ν ′ ≪ α , ν , τ ≪ 1 . Suppose that G G G is a robust ( ν , τ ) (\nu,\tau) ( ν , τ ) -outexpander on n n n vertices and satisfies δ 0 ( G ) ≥ α n \delta^0(G) \ge\alpha n δ 0 ( G ) ≥ α n . Then, for every integer ξ n ≤ m ≤ n \xi n \le m \le n ξ n ≤ m ≤ n , a subset S S S chosen uniformly at random from all m m m -subsets of V ( G ) V(G) V ( G ) satisfies P [ G [ S ] is a robust ( ν ′ , 4 τ ) -outexpander ] ≥ 1 − 1 / n 2 \mathbb{P}[G[S]\text{ is a robust }(\nu',4\tau)\text{-outexpander}] \ge1-1/n^2 P [ G [ S ] is a robust ( ν ′ , 4 τ ) -outexpander ] ≥ 1 − 1/ n 2 .
Lemma 2.12 (Lo and Patel [10 ] ). Let 0 < ν ≤ τ ≤ γ / 16 < 1 / 16 0 < \nu\le\tau\le\gamma/16 < 1/16 0 < ν ≤ τ ≤ γ /16 < 1/16 . There exists a positive integer n 0 n_0 n 0 such that for all n ≥ n 0 n \ge n_0 n ≥ n 0 , every n n n -vertex digraph D D D with δ 0 ( D ) ≥ γ n \delta^0(D) \ge\gamma n δ 0 ( D ) ≥ γ n which is a robust ( ν , τ ) (\nu,\tau) ( ν , τ ) -outexpander contains a cycle of every length ν n / 2 ≤ ℓ ≤ n \nu n/2 \le\ell\le n ν n /2 ≤ ℓ ≤ n .
Other useful tools
Lemma 2.13 (Hoeffding inequality [7 ] ). Let X = X 1 + ⋯ + X q X=X_1+\cdots+X_q X = X 1 + ⋯ + X q , where the X i X_i X i are independent random variables, each having a binomial or hypergeometric distribution with sample size m i m_i m i . Set M = ∑ i = 1 q m i M=\sum_{i=1}^{q}m_i M = ∑ i = 1 q m i . Then, for every t ≥ 0 t\ge0 t ≥ 0 ,
P ( ∣ X − E X ∣ ≥ t ) ≤ 2 exp ( − 2 t 2 M ) . \mathbb{P}(|X-\mathbb{E}X|\ge t)\le2\exp\left(-\frac{2t^2}{M}\right). P ( ∣ X − E X ∣ ≥ t ) ≤ 2 exp ( − M 2 t 2 ) .
Lemma 2.14 (Markov’s inequality). Let X X X be a nonnegative random variable. Then, for every a > 0 a>0 a > 0 , P [ X ≥ a ] ≤ E [ X ] / a \mathbb{P}[X\ge a]\le\mathbb{E}[X]/a P [ X ≥ a ] ≤ E [ X ] / a .
Proposition 2.15. Let r , t r,t r , t be positive integers and let 0 ≤ k ≤ r 0\le k\le r 0 ≤ k ≤ r . Then
( t r t k ) ≤ ( r + 1 ) t − 1 ( r k ) t . \binom{tr}{tk}\le(r+1)^{t-1}\binom{r}{k}^{t}. ( t k t r ) ≤ ( r + 1 ) t − 1 ( k r ) t . Proof. Let a 1 , … , a t a_1,\ldots,a_t a 1 , … , a t be integers such that 0 ≤ a i ≤ r 0\le a_i\le r 0 ≤ a i ≤ r for every i ∈ [ t ] i\in[t] i ∈ [ t ] and ∑ i = 1 t a i = t k \sum_{i=1}^{t}a_i=tk ∑ i = 1 t a i = t k . Then ∏ i = 1 t ( r a i ) ≤ ( r k ) t \prod_{i=1}^{t}\binom{r}{a_i}\le\binom{r}{k}^{t} ∏ i = 1 t ( a i r ) ≤ ( k r ) t . Since there are at most ( r + 1 ) t − 1 (r+1)^{t-1} ( r + 1 ) t − 1 choices for ( a 1 , … , a t ) (a_1,\ldots,a_t) ( a 1 , … , a t ) , Vandermonde’s identity gives
( t r t k ) = ∑ a 1 + ⋯ + a t = t k ( r a 1 ) ( r a 2 ) ⋯ ( r a t ) ≤ ( r + 1 ) t − 1 ( r k ) t . \binom{tr}{tk}=\sum_{a_1+\cdots+a_t=tk}\binom{r}{a_1}\binom{r}{a_2}\cdots\binom{r}{a_t}\le(r+1)^{t-1}\binom{r}{k}^{t}. ( t k t r ) = a 1 + ⋯ + a t = t k ∑ ( a 1 r ) ( a 2 r ) ⋯ ( a t r ) ≤ ( r + 1 ) t − 1 ( k r ) t .
Balanced cycles with at least four partite classes
We begin with some notation and two auxiliary propositions. For a vertex v v v of a multipartite tournament and a partite class X X X , let s ( v , X ) = d + ( v , X ) − d − ( v , X ) s(v,X)=d^+(v,X)-d^-(v,X) s ( v , X ) = d + ( v , X ) − d − ( v , X ) . Clearly, s ( v , X ) = 0 s(v,X)=0 s ( v , X ) = 0 if v ∈ X v\in X v ∈ X .
Proposition 3.1. Let G G G be a c c c -partite tournament with partite classes V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c , each of size r r r . For any distinct i , j , k ∈ [ c ] i,j,k\in[c] i , j , k ∈ [ c ] , the number of triangles in G [ V i ∪ V j ∪ V k ] G[V_i\cup V_j\cup V_k] G [ V i ∪ V j ∪ V k ] is
1 4 ( r 3 − ∑ x ∈ V i s ( x , V j ) s ( x , V k ) − ∑ y ∈ V j s ( y , V i ) s ( y , V k ) − ∑ z ∈ V k s ( z , V i ) s ( z , V j ) ) . \frac{1}{4}\left(r^3-\sum_{x\in V_i}s(x,V_j)s(x,V_k)-\sum_{y\in V_j}s(y,V_i)s(y,V_k)-\sum_{z\in V_k}s(z,V_i)s(z,V_j)\right). 4 1 r 3 − x ∈ V i ∑ s ( x , V j ) s ( x , V k ) − y ∈ V j ∑ s ( y , V i ) s ( y , V k ) − z ∈ V k ∑ s ( z , V i ) s ( z , V j ) . Proof. Let t t t denote the number of triangles in G [ V i ∪ V j ∪ V k ] G[V_i\cup V_j\cup V_k] G [ V i ∪ V j ∪ V k ] . Every triple ( x , y , z ) ∈ V i × V j × V k (x,y,z)\in V_i\times V_j\times V_k ( x , y , z ) ∈ V i × V j × V k induces either a triangle or a transitive tournament. Hence
r 3 − t = ∑ x ∈ V i d + ( x , V j ) d + ( x , V k ) + ∑ y ∈ V j d + ( y , V i ) d + ( y , V k ) + ∑ z ∈ V k d + ( z , V i ) d + ( z , V j ) . r^3-t=\sum_{x\in V_i}d^+(x,V_j)d^+(x,V_k)+\sum_{y\in V_j}d^+(y,V_i)d^+(y,V_k)+\sum_{z\in V_k}d^+(z,V_i)d^+(z,V_j). r 3 − t = x ∈ V i ∑ d + ( x , V j ) d + ( x , V k ) + y ∈ V j ∑ d + ( y , V i ) d + ( y , V k ) + z ∈ V k ∑ d + ( z , V i ) d + ( z , V j ) . For every i ≠ j i\ne j i = j with v ∈ V i v\in V_i v ∈ V i , we have 2 d + ( v , V j ) = r + s ( v , V j ) 2d^+(v,V_j)=r+s(v,V_j) 2 d + ( v , V j ) = r + s ( v , V j ) . Thus, we obtain
4 t = r 3 − ∑ x ∈ V i s ( x , V j ) s ( x , V k ) − ∑ y ∈ V j s ( y , V i ) s ( y , V k ) − ∑ z ∈ V k s ( z , V i ) s ( z , V j ) . 4t=r^3-\sum_{x\in V_i}s(x,V_j)s(x,V_k)-\sum_{y\in V_j}s(y,V_i)s(y,V_k)-\sum_{z\in V_k}s(z,V_i)s(z,V_j). 4 t = r 3 − x ∈ V i ∑ s ( x , V j ) s ( x , V k ) − y ∈ V j ∑ s ( y , V i ) s ( y , V k ) − z ∈ V k ∑ s ( z , V i ) s ( z , V j ) .
Proposition 3.2. For all integers c ≥ 4 c \ge4 c ≥ 4 and k ≥ 1 k \ge1 k ≥ 1 and every ξ > 0 \xi> 0 ξ > 0 , there exists r 0 = r 0 ( c , k , ξ ) r_0 = r_0(c,k,\xi) r 0 = r 0 ( c , k , ξ ) such that the following holds. Let G G G be a c c c -partite tournament with partite classes V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c , each of size r ≥ r 0 r \ge r_0 r ≥ r 0 . If G G G contains at least ξ r c \xi r^c ξ r c balanced cycles of the form v 1 v 2 ⋯ v c v 1 v_1v_2 \cdots v_cv_1 v 1 v 2 ⋯ v c v 1 , where v i ∈ V i v_i \in V_i v i ∈ V i for every i ∈ [ c ] i \in[c] i ∈ [ c ] , then G G G contains a k k k -balanced cycle.
Proof. Define a c c c -partite c c c -uniform hypergraph H \mathcal{H} H with vertex classes V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c by declaring that { v 1 , … , v c } ∈ E ( H ) \{v_1,\ldots,v_c\} \in E(\mathcal{H}) { v 1 , … , v c } ∈ E ( H ) if and only if v 1 ⋯ v c v 1 v_1 \cdots v_cv_1 v 1 ⋯ v c v 1 is a balanced cycle in G G G . We have e ( H ) ≥ ξ r c e(\mathcal{H}) \ge\xi r^c e ( H ) ≥ ξ r c . By Lemma 2.10 , there exist sets U i = { u i , 1 , … , u i , k } ⊆ V i U_i = \{u_{i,1},\ldots,u_{i,k}\} \subseteq V_i U i = { u i , 1 , … , u i , k } ⊆ V i for i ∈ [ c ] i \in[c] i ∈ [ c ] that form a copy of K k , … , k ( c ) K^{(c)}_{k,\ldots,k} K k , … , k ( c ) in H \mathcal{H} H . By the definition of H \mathcal{H} H , every edge between U i U_i U i and U i + 1 U_{i+1} U i + 1 is directed from U i U_i U i to U i + 1 U_{i+1} U i + 1 for every i ∈ [ c ] i \in[c] i ∈ [ c ] , where indices are taken modulo c c c . Consequently,
u 1 , 1 , u 2 , 1 , … , u c , 1 , u 1 , 2 , u 2 , 2 , … , u c , 2 , … , u 1 , k , u 2 , k , … , u c , k , u 1 , 1 u_{1,1},u_{2,1},\ldots,u_{c,1},u_{1,2},u_{2,2},\ldots,u_{c,2},\ldots,u_{1,k},u_{2,k},\ldots,u_{c,k},u_{1,1} u 1 , 1 , u 2 , 1 , … , u c , 1 , u 1 , 2 , u 2 , 2 , … , u c , 2 , … , u 1 , k , u 2 , k , … , u c , k , u 1 , 1
forms a k k k -balanced cycle in G G G .
Long cycles
Lemma 3.3. There exists an integer N N N such that every regular c c c -partite tournament G G G with c ≥ 4 c \ge4 c ≥ 4 and common partite size r r r contains a k k k -balanced cycle whenever 1 ≤ k ≤ r 1 \le k \le r 1 ≤ k ≤ r and c k ≥ N ck \ge N c k ≥ N .
Proof. Let V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c be the partite classes of G G G . For each i ∈ [ c ] i \in[c] i ∈ [ c ] , choose a k k k -subset U i U_i U i of V i V_i V i uniformly at random. Set U = ⋃ i = 1 c U i U = \bigcup_{i=1}^{c} U_i U = ⋃ i = 1 c U i and H = G [ U ] H = G[U] H = G [ U ] . For each fixed v ∈ V i v \in V_i v ∈ V i , we have E [ d G + ( v , U ) ] = k r d G + ( v ) = k ( c − 1 ) 2 \mathbb{E}[d_G^+(v,U)] = \frac{k}{r}d_G^+(v) = \frac{k(c-1)}{2} E [ d G + ( v , U )] = r k d G + ( v ) = 2 k ( c − 1 ) . Thus, by Lemma 2.13 , for each fixed v ∈ V ( G ) v \in V(G) v ∈ V ( G )
P ( ∣ d H + ( v ) − ( c − 1 ) k 2 ∣ > ( c − 3 ) k 4 ) ≤ 2 exp ( − ( c − 3 ) 2 k 8 ( c − 1 ) ) . \mathbb{P}\left(\left|d_H^+(v)-\frac{(c-1)k}{2}\right|>\frac{(c-3)k}{4}\right)\le2\exp\left(-\frac{(c-3)^2k}{8(c-1)}\right). P ( d H + ( v ) − 2 ( c − 1 ) k > 4 ( c − 3 ) k ) ≤ 2 exp ( − 8 ( c − 1 ) ( c − 3 ) 2 k ) .
By the union bound, and taking N N N sufficiently large, we obtain 2 c k ⋅ exp ( − ( c − 3 ) 2 k 8 ( c − 1 ) ) ≤ 2 c k ⋅ exp ( − c k 96 ) < 1 2ck\cdot\exp\left(-\frac{(c-3)^2k}{8(c-1)}\right)\le2ck\cdot\exp\left(-\frac{ck}{96}\right)<1 2 c k ⋅ exp ( − 8 ( c − 1 ) ( c − 3 ) 2 k ) ≤ 2 c k ⋅ exp ( − 96 c k ) < 1 . Hence there exists H ⊆ G H \subseteq G H ⊆ G satisfying
∣ d H + ( v ) − ( c − 1 ) k 2 ∣ ≤ ( c − 3 ) k 4 \left|d_H^+(v)-\frac{(c-1)k}{2}\right|\le\frac{(c-3)k}{4} d H + ( v ) − 2 ( c − 1 ) k ≤ 4 ( c − 3 ) k
for every v ∈ V ( H ) v \in V(H) v ∈ V ( H ) . Since d H + ( v ) + d H − ( v ) = ( c − 1 ) k d_H^+(v)+d_H^-(v)=(c-1)k d H + ( v ) + d H − ( v ) = ( c − 1 ) k , we obtain
Δ 0 ( H ) − δ 0 ( H ) ≤ ( c − 3 ) k 2 < ( c − 3 ) k + 2 2 . \Delta^0(H)-\delta^0(H)\le\frac{(c-3)k}{2}<\frac{(c-3)k+2}{2}. Δ 0 ( H ) − δ 0 ( H ) ≤ 2 ( c − 3 ) k < 2 ( c − 3 ) k + 2 .
By Proposition 2.5 , H H H contains a Hamilton cycle, which is k k k -balanced in G G G .
Short cycles
Lemma 3.4. For all integers c ≥ 5 c \ge5 c ≥ 5 and K ≥ 1 K \ge1 K ≥ 1 , there exists an integer r 0 = r 0 ( c , K ) ≥ K r_0=r_0(c,K)\ge K r 0 = r 0 ( c , K ) ≥ K such that every regular c c c -partite tournament with common partite size r ≥ r 0 r \ge r_0 r ≥ r 0 contains a k k k -balanced cycle for every 1 ≤ k ≤ K 1 \le k \le K 1 ≤ k ≤ K .
Proof. Let V 1 , … , V c V_1,\ldots,V_c V 1 , … , V c be the partite classes of G G G . Choose one vertex v i v_i v i from each class V i V_i V i independently and uniformly at random, and let T T T be the induced tournament. We claim that T T T is strongly connected with probability at least 1 / 100 1/100 1/100 .
We first bound the probability that T T T has a source or a sink. By Proposition 2.6 , for v ∈ V i v \in V_i v ∈ V i we have
P ( v is a source ∣ v ∈ V ( T ) ) = ∏ j ≠ i d + ( v , V j ) r ≤ 2 − ( c − 1 ) . \mathbb{P}(v\text{ is a source}\mid v\in V(T))=\prod_{j\ne i}\frac{d^+(v,V_j)}{r}\le2^{-(c-1)}. P ( v is a source ∣ v ∈ V ( T )) = j = i ∏ r d + ( v , V j ) ≤ 2 − ( c − 1 ) .
The same bound holds for the probability that v v v is a sink. By the union bound we have
P ( T has a source or a sink ) ≤ 2 c 2 c − 1 . (1) \mathbb{P}(T\text{ has a source or a sink})\le\frac{2c}{2^{c-1}}. \tag*{(1)} P ( T has a source or a sink ) ≤ 2 c − 1 2 c . (1)
If c = 5 c=5 c = 5 , a tournament with neither a source nor a sink is strongly connected, since otherwise its first and last strong components each have at least three vertices. Hence P ( T is strongly connected ) ≥ 3 / 8 > 1 / 100 \mathbb{P}(T\text{ is strongly connected}) \ge3/8 > 1/100 P ( T is strongly connected ) ≥ 3/8 > 1/100 . Now suppose that c ≥ 6 c \ge6 c ≥ 6 . If T T T is not strongly connected and has neither a source nor a sink, let Q Q Q be its first strong component. Then ∣ Q ∣ ≥ 3 |Q| \ge3 ∣ Q ∣ ≥ 3 and c − ∣ Q ∣ ≥ 3 c-|Q| \ge3 c − ∣ Q ∣ ≥ 3 . Moreover, ∑ v ∈ Q d T + ( v ) = e ( Q ) + ∣ Q ∣ ( c − ∣ Q ∣ ) \sum_{v\in Q}d_T^+(v)=e(Q)+|Q|(c-|Q|) ∑ v ∈ Q d T + ( v ) = e ( Q ) + ∣ Q ∣ ( c − ∣ Q ∣ ) . Consequently,
∑ v ∈ V ( T ) ( d T + ( v ) − c − 1 2 ) 2 = ∑ v ∈ Q ( d T + ( v ) − c − 1 2 ) 2 + ∑ v ∉ Q ( d T + ( v ) − c − 1 2 ) 2 ≥ ( ∑ v ∈ Q ( d T + ( v ) − c − 1 2 ) ) 2 ∣ Q ∣ + ( ∑ v ∉ Q ( d T + ( v ) − c − 1 2 ) ) 2 c − ∣ Q ∣ = ∣ Q ∣ ( c − ∣ Q ∣ ) c 4 ≥ 3 c ( c − 3 ) 4 . \begin{aligned}
\sum_{v\in V(T)}\left(d_T^+(v)-\frac{c-1}{2}\right)^2
=\sum_{v\in Q}\left(d_T^+(v)-\frac{c-1}{2}\right)^2+\sum_{v\notin Q}\left(d_T^+(v)-\frac{c-1}{2}\right)^2 \\
&\ge\frac{\left(\sum_{v\in Q}\left(d_T^+(v)-\frac{c-1}{2}\right)\right)^2}{|Q|}
+\frac{\left(\sum_{v\notin Q}\left(d_T^+(v)-\frac{c-1}{2}\right)\right)^2}{c-|Q|}
=\frac{|Q|(c-|Q|)c}{4} \\
&\ge\frac{3c(c-3)}{4}.
\end{aligned} v ∈ V ( T ) ∑ ( d T + ( v ) − 2 c − 1 ) 2 = v ∈ Q ∑ ( d T + ( v ) − 2 c − 1 ) 2 + v ∈ / Q ∑ ( d T + ( v ) − 2 c − 1 ) 2 ≥ ∣ Q ∣ ( ∑ v ∈ Q ( d T + ( v ) − 2 c − 1 ) ) 2 + c − ∣ Q ∣ ( ∑ v ∈ / Q ( d T + ( v ) − 2 c − 1 ) ) 2 = 4 ∣ Q ∣ ( c − ∣ Q ∣ ) c ≥ 4 3 c ( c − 3 ) .
For each v ∈ T v\in T v ∈ T , we have E ( d T + ( v ) ) = ( c − 1 ) / 2 \mathbb{E}(d_T^+(v))=(c-1)/2 E ( d T + ( v )) = ( c − 1 ) /2 , and E ( ( d T + ( v ) − ( c − 1 ) / 2 ) 2 ) = Var ( d T + ( v ) ) ≤ ( c − 1 ) / 4 \mathbb{E}((d_T^+(v)-(c-1)/2)^2)=\operatorname{Var}(d_T^+(v))\le(c-1)/4 E (( d T + ( v ) − ( c − 1 ) /2 ) 2 ) = Var ( d T + ( v )) ≤ ( c − 1 ) /4 . Hence, by Markov’s inequality
P ( ∑ v ∈ V ( T ) ( d T + ( v ) − c − 1 2 ) 2 ≥ 3 c ( c − 3 ) 4 ) ≤ 4 E ( ∑ v ∈ V ( T ) ( d T + ( v ) − c − 1 2 ) 2 ) 3 c ( c − 3 ) ≤ c − 1 3 ( c − 3 ) . \mathbb{P}\left(\sum_{v\in V(T)}\left(d_T^+(v)-\frac{c-1}{2}\right)^2\ge\frac{3c(c-3)}{4}\right)
\le\frac{4\mathbb{E}\left(\sum_{v\in V(T)}\left(d_T^+(v)-\frac{c-1}{2}\right)^2\right)}{3c(c-3)}
\le\frac{c-1}{3(c-3)}. P v ∈ V ( T ) ∑ ( d T + ( v ) − 2 c − 1 ) 2 ≥ 4 3 c ( c − 3 ) ≤ 3 c ( c − 3 ) 4 E ( ∑ v ∈ V ( T ) ( d T + ( v ) − 2 c − 1 ) 2 ) ≤ 3 ( c − 3 ) c − 1 .
Combining (1) and (2) gives P ( T is strongly connected ) ≥ 1 − 2 c 2 c − 1 − c − 1 3 ( c − 3 ) ≥ 1 100 \mathbb{P}(T\text{ is strongly connected})\ge1-\frac{2c}{2^{c-1}}-\frac{c-1}{3(c-3)}\ge\frac{1}{100} P ( T is strongly connected ) ≥ 1 − 2 c − 1 2 c − 3 ( c − 3 ) c − 1 ≥ 100 1 . Therefore, at least r c / 100 r^c/100 r c /100 sets induce a strongly connected tournament, and hence contain a Hamilton cycle by Proposition 2.2 . By the pigeonhole principle, after relabeling the classes if necessary, at least r c / ( 100 ( c − 1 ) ! ) r^c/(100(c-1)!) r c / ( 100 ( c − 1 )!) cycles with the cyclic order ( v 1 , v 2 , ⋯ , v c , v 1 ) (v_1,v_2,\cdots,v_c,v_1) ( v 1 , v 2 , ⋯ , v c , v 1 ) where v i ∈ V i v_i\in V_i v i ∈ V i . Applying Proposition 3.2 with ξ = 1 / ( 100 ( c − 1 ) ! ) \xi=1/(100(c-1)!) ξ = 1/ ( 100 ( c − 1 )!) yields the required k k k -balanced cycles.
The case c = 4 c=4 c = 4 differs slightly from the case c ≥ 5 c\ge5 c ≥ 5 . Volkmann [14 ] constructed an infinite family of regular 4-partite tournaments containing no balanced directed 4-cycle. Thus the preceding lemma cannot be extended to c = 4 c=4 c = 4 with k = 1 k=1 k = 1 included. However, the following lemma shows that k = 1 k=1 k = 1 is the only exception.
Lemma 3.5. For every integer K ≥ 2 K\ge2 K ≥ 2 , there exists an integer r 0 = r 0 ( K ) ≥ K r_0=r_0(K)\ge K r 0 = r 0 ( K ) ≥ K such that every regular 4-partite tournament with common partite size r ≥ r 0 r\ge r_0 r ≥ r 0 contains a k k k -balanced cycle for every $2\le k\le K.
Proof. Choose 1 / r ≪ σ ≪ η ≪ 1 / K ≪ 1 1/r\ll\sigma\ll\eta\ll1/K\ll1 1/ r ≪ σ ≪ η ≪ 1/ K ≪ 1 . Write V 1 , V 2 , V 3 , V 4 V_1,V_2,V_3,V_4 V 1 , V 2 , V 3 , V 4 for the partite classes, and let b b b denote the number of balanced 4-cycles. If b ≥ σ r 4 b\ge\sigma r^4 b ≥ σ r 4 , the conclusion follows from Proposition 3.2 with parameters ξ = σ / 6 \xi=\sigma/6 ξ = σ /6 and c = 4 c=4 c = 4 . Hence we may assume that b < σ r 4 b<\sigma r^4 b < σ r 4 .
Claim 3.6. We have ∑ v ∈ V ( G ) ∑ i ∈ [ 4 ] s ( v , V i ) 2 ≤ 8 σ r 3 \sum_{v\in V(G)}\sum_{i\in[4]}s(v,V_i)^2\le8\sigma r^3 ∑ v ∈ V ( G ) ∑ i ∈ [ 4 ] s ( v , V i ) 2 ≤ 8 σ r 3 . Moreover, for all distinct i , j ∈ [ 4 ] i,j\in[4] i , j ∈ [ 4 ] , ∑ v ∈ V i ∣ d + ( v , V j ) − r / 2 ∣ ≤ 2 σ r 2 \sum_{v\in V_i}|d^+(v,V_j)-r/2|\le\sqrt{2\sigma}\,r^2 ∑ v ∈ V i ∣ d + ( v , V j ) − r /2∣ ≤ 2 σ r 2 .
Proof. By Proposition 3.1 , the number of triangles in G G G is
r 3 + 1 8 ∑ v ∈ V ( G ) ∑ i ∈ [ 4 ] s ( v , V i ) 2 . r^3+\frac{1}{8}\sum_{v\in V(G)}\sum_{i\in[4]}s(v,V_i)^2. r 3 + 8 1 v ∈ V ( G ) ∑ i ∈ [ 4 ] ∑ s ( v , V i ) 2 .
On the other hand, every balanced 4-set induces at most one triangle, unless it contains a 4-cycle, in which case it induces two. Since each triangle is contained in exactly r r r balanced 4-sets, the number of triangles is at most ( r 4 + b ) / r ≤ r 3 + σ r 3 (r^4+b)/r\le r^3+\sigma r^3 ( r 4 + b ) / r ≤ r 3 + σ r 3 . Thus, ∑ v ∈ V ( G ) ∑ i ∈ [ 4 ] s ( v , V i ) 2 ≤ 8 σ r 3 \sum_{v\in V(G)}\sum_{i\in[4]}s(v,V_i)^2\le8\sigma r^3 ∑ v ∈ V ( G ) ∑ i ∈ [ 4 ] s ( v , V i ) 2 ≤ 8 σ r 3 . Moreover,
∑ v ∈ V i ∣ d + ( v , V j ) − r 2 ∣ = 1 2 ∑ v ∈ V i ∣ s ( v , V j ) ∣ ≤ 1 2 r ∑ v ∈ V i s ( v , V j ) 2 ≤ 2 σ r 2 . (2) \sum_{v\in V_i}\left|d^+(v,V_j)-\frac{r}{2}\right|
=\frac{1}{2}\sum_{v\in V_i}|s(v,V_j)|
\le\frac{1}{2}\sqrt{r\sum_{v\in V_i}s(v,V_j)^2}
\le\sqrt{2\sigma}\,r^2. \tag*{(2)} v ∈ V i ∑ d + ( v , V j ) − 2 r = 2 1 v ∈ V i ∑ ∣ s ( v , V j ) ∣ ≤ 2 1 r v ∈ V i ∑ s ( v , V j ) 2 ≤ 2 σ r 2 . (2)
The indegree estimate follows from d + ( v , V j ) + d − ( v , V j ) = r d^{+}(v,V_j)+d^{-}(v,V_j)=r d + ( v , V j ) + d − ( v , V j ) = r . ■
For each i ∈ [ 4 ] i\in[4] i ∈ [ 4 ] and i ≠ j i\ne j i = j , let A i : = ⋃ j ≠ i { v ∈ V i : ∣ s ( v , V j ) ∣ > 2 η r } A_i:=\bigcup_{j\ne i}\{v\in V_i:|s(v,V_j)|>2\eta r\} A i := ⋃ j = i { v ∈ V i : ∣ s ( v , V j ) ∣ > 2 η r } . By Claim 3.6 , we have
∣ A i ∣ ≤ ∑ v ∈ V ( G ) ∑ i ∈ [ 4 ] s ( v , V i ) 2 / ( 2 η r ) 2 ≤ η r . |A_i|\le\sum_{v\in V(G)}\sum_{i\in[4]}s(v,V_i)^2/(2\eta r)^2\le\eta r. ∣ A i ∣ ≤ v ∈ V ( G ) ∑ i ∈ [ 4 ] ∑ s ( v , V i ) 2 / ( 2 η r ) 2 ≤ η r .
For an edge x y xy x y , let N x y N_{xy} N x y denote the number of balanced 4 4 4 -cycles containing x y xy x y , and let E = { x y ∈ E ( G ) : N x y > η r 2 } \mathcal{E}=\{xy\in E(G):N_{xy}>\eta r^2\} E = { x y ∈ E ( G ) : N x y > η r 2 } . Since ∑ x y ∈ E ( G ) N x y = 4 b \sum_{xy\in E(G)}N_{xy}=4b ∑ x y ∈ E ( G ) N x y = 4 b and σ ≪ η \sigma\ll\eta σ ≪ η , we have ∣ E ∣ ≤ 4 σ r 4 / η r 2 ≤ η 2 r 2 |\mathcal{E}|\le4\sigma r^4/\eta r^2\le\eta^2r^2 ∣ E ∣ ≤ 4 σ r 4 / η r 2 ≤ η 2 r 2 . Let B i B_i B i be the set of vertices in V i V_i V i incident with more than η r \eta r η r edges of E \mathcal{E} E . Since ∣ B i ∣ η r ≤ ∑ v ∈ V i d E ( v ) ≤ ∣ E ∣ |B_i|\eta r\le\sum_{v\in V_i}d_{\mathcal{E}}(v)\le|\mathcal{E}| ∣ B i ∣ η r ≤ ∑ v ∈ V i d E ( v ) ≤ ∣ E ∣ , we have ∣ B i ∣ ≤ η r |B_i|\le\eta r ∣ B i ∣ ≤ η r . Let V i ′ = V i ∖ ( A i ∪ B i ) V_i'=V_i\setminus(A_i\cup B_i) V i ′ = V i ∖ ( A i ∪ B i ) and we have for every v ∈ V i ′ v\in V_i' v ∈ V i ′ and j ≠ i j\ne i j = i ,
( 1 2 − 3 η ) r ≤ d ± ( v , V j ′ ) ≤ ( 1 2 + η ) r , (3) \left(\frac{1}{2}-3\eta\right)r\le d^{\pm}(v,V_j')\le\left(\frac{1}{2}+\eta\right)r, \tag*{(3)} ( 2 1 − 3 η ) r ≤ d ± ( v , V j ′ ) ≤ ( 2 1 + η ) r , (3)
since ∣ d ± ( v , V j ) − r / 2 ∣ = ∣ s ( v , V j ) ∣ / 2 ≤ η r |d^{\pm}(v,V_j)-r/2|=|s(v,V_j)|/2\le\eta r ∣ d ± ( v , V j ) − r /2∣ = ∣ s ( v , V j ) ∣/2 ≤ η r for each v ∈ V i v\in V_i v ∈ V i and at most 2 η r 2\eta r 2 η r vertices are removed from V j V_j V j .
An edge is good if both end-vertex lie in ⋃ i V i ′ \bigcup_iV_i' ⋃ i V i ′ and the edge does not belong to E \mathcal{E} E . A path or cycle is good if all its edges are good.
Claim 3.7. Every good edge x y xy x y can be replaced by at least r 2 / 4 r^2/4 r 2 /4 good balanced ( x , y ) (x,y) ( x , y ) -paths of length 3.
Proof. Let x y xy x y be a good edge. By relabelling the classes, we may assume that x ∈ V 1 ′ x\in V_1' x ∈ V 1 ′ and y ∈ V 2 ′ y\in V_2' y ∈ V 2 ′ . Let P x y \mathcal{P}_{xy} P x y be the family of ( x , y ) (x,y) ( x , y ) -paths of length 3 with one internal vertex in each of V 3 , V 4 V_3,V_4 V 3 , V 4 , and let P y x \mathcal{P}_{yx} P y x be the family of such ( y , x ) (y,x) ( y , x ) -paths. For i ∈ { 3 , 4 } i\in\{3,4\} i ∈ { 3 , 4 } , let X i = N + ( x ) ∩ V i X_i=N^{+}(x)\cap V_i X i = N + ( x ) ∩ V i and Y i = N + ( y ) ∩ V i Y_i=N^{+}(y)\cap V_i Y i = N + ( y ) ∩ V i . By definition, ∣ P x y ∣ = e G ( X 3 , V 4 ∖ Y 4 ) + e G ( X 4 , V 3 ∖ Y 3 ) |\mathcal{P}_{xy}|=e_G(X_3,V_4\setminus Y_4)+e_G(X_4,V_3\setminus Y_3) ∣ P x y ∣ = e G ( X 3 , V 4 ∖ Y 4 ) + e G ( X 4 , V 3 ∖ Y 3 ) and ∣ P y x ∣ = e G ( Y 3 , V 4 ∖ X 4 ) + e G ( Y 4 , V 3 ∖ X 3 ) |\mathcal{P}_{yx}|=e_G(Y_3,V_4\setminus X_4)+e_G(Y_4,V_3\setminus X_3) ∣ P y x ∣ = e G ( Y 3 , V 4 ∖ X 4 ) + e G ( Y 4 , V 3 ∖ X 3 ) . Consequently,
∣ P x y ∣ + ∣ P y x ∣ = e G ( X 3 , V 4 ) + e G ( Y 3 , V 4 ) + e G ( X 4 , V 3 ) + e G ( Y 4 , V 3 ) − ∣ X 3 ∣ ∣ Y 4 ∣ − ∣ X 4 ∣ ∣ Y 3 ∣ . |\mathcal{P}_{xy}|+|\mathcal{P}_{yx}|=e_G(X_3,V_4)+e_G(Y_3,V_4)+e_G(X_4,V_3)+e_G(Y_4,V_3)-|X_3||Y_4|-|X_4||Y_3|. ∣ P x y ∣ + ∣ P y x ∣ = e G ( X 3 , V 4 ) + e G ( Y 3 , V 4 ) + e G ( X 4 , V 3 ) + e G ( Y 4 , V 3 ) − ∣ X 3 ∣∣ Y 4 ∣ − ∣ X 4 ∣∣ Y 3 ∣.
By Claim 3.6 , for every Z ∈ { X 3 , Y 3 } Z\in\{X_3,Y_3\} Z ∈ { X 3 , Y 3 } we have e G ( Z , V 4 ) ≥ r 2 ∣ Z ∣ − 2 σ r 2 e_G(Z,V_4)\ge\frac{r}{2}|Z|-\sqrt{2\sigma}\,r^2 e G ( Z , V 4 ) ≥ 2 r ∣ Z ∣ − 2 σ r 2 , and similarly, for Z ∈ { X 4 , Y 4 } Z\in\{X_4,Y_4\} Z ∈ { X 4 , Y 4 } , e G ( Z , V 3 ) ≥ r 2 ∣ Z ∣ − 2 σ r 2 e_G(Z,V_3)\ge\frac{r}{2}|Z|-\sqrt{2\sigma}\,r^2 e G ( Z , V 3 ) ≥ 2 r ∣ Z ∣ − 2 σ r 2 . Moreover, since x y xy x y is a good edge, we have ∣ ∣ X i ∣ − r 2 ∣ ≤ η r \left||X_i|-\frac{r}{2}\right|\le\eta r ∣ X i ∣ − 2 r ≤ η r and ∣ ∣ Y i ∣ − r 2 ∣ ≤ η r \left||Y_i|-\frac{r}{2}\right|\le\eta r ∣ Y i ∣ − 2 r ≤ η r for i ∈ { 3 , 4 } i\in\{3,4\} i ∈ { 3 , 4 } . Therefore, ∣ P x y ∣ + ∣ P y x ∣ |\mathcal{P}_{xy}|+|\mathcal{P}_{yx}| ∣ P x y ∣ + ∣ P y x ∣ is at least
r 2 ( ∣ X 3 ∣ + ∣ X 4 ∣ + ∣ Y 3 ∣ + ∣ Y 4 ∣ ) − ∣ X 3 ∣ ∣ Y 4 ∣ − ∣ X 4 ∣ ∣ Y 3 ∣ − 4 2 σ r 2 ≥ r 2 2 − ( ∣ X 3 ∣ − r 2 ) ( ∣ Y 4 ∣ − r 2 ) − ( ∣ X 4 ∣ − r 2 ) ( ∣ Y 3 ∣ − r 2 ) − 4 2 σ r 2 ≥ ( 1 2 − 2 η 2 − 4 2 σ ) r 2 . \begin{aligned}
\frac{r}{2}\left(|X_3|+|X_4|+|Y_3|+|Y_4|\right)-|X_3||Y_4|-|X_4||Y_3|-4\sqrt{2\sigma}\,r^2 \\
&\ge\frac{r^2}{2}-\left(|X_3|-\frac{r}{2}\right)\left(|Y_4|-\frac{r}{2}\right)-\left(|X_4|-\frac{r}{2}\right)\left(|Y_3|-\frac{r}{2}\right)-4\sqrt{2\sigma}\,r^2 \\
&\ge\left(\frac{1}{2}-2\eta^2-4\sqrt{2\sigma}\right)r^2.
\end{aligned} 2 r ( ∣ X 3 ∣ + ∣ X 4 ∣ + ∣ Y 3 ∣ + ∣ Y 4 ∣ ) − ∣ X 3 ∣∣ Y 4 ∣ − ∣ X 4 ∣∣ Y 3 ∣ − 4 2 σ r 2 ≥ 2 r 2 − ( ∣ X 3 ∣ − 2 r ) ( ∣ Y 4 ∣ − 2 r ) − ( ∣ X 4 ∣ − 2 r ) ( ∣ Y 3 ∣ − 2 r ) − 4 2 σ r 2 ≥ ( 2 1 − 2 η 2 − 4 2 σ ) r 2 .
Since every path in P y x \mathcal{P}_{yx} P y x , together with x y xy x y , forms a balanced 4 4 4 -cycle, we have ∣ P y x ∣ = N x y ≤ η r 2 |\mathcal{P}_{yx}|=N_{xy}\le\eta r^2 ∣ P y x ∣ = N x y ≤ η r 2 . By σ ≪ η \sigma\ll\eta σ ≪ η , we have ∣ P x y ∣ ≥ ( 1 / 2 − η − 2 η 2 − 4 2 σ ) r 2 ≥ ( 1 / 2 − 2 η ) r 2 |\mathcal{P}_{xy}|\ge(1/2-\eta-2\eta^2-4\sqrt{2\sigma})r^2\ge(1/2-2\eta)r^2 ∣ P x y ∣ ≥ ( 1/2 − η − 2 η 2 − 4 2 σ ) r 2 ≥ ( 1/2 − 2 η ) r 2 .
It remains to exclude paths in P x y \mathcal{P}_{xy} P x y that are not good. First, since ∣ V i ∖ V i ′ ∣ ≤ 2 η r |V_i\setminus V_i'|\le2\eta r ∣ V i ∖ V i ′ ∣ ≤ 2 η r for each i ∈ [ 4 ] i\in[4] i ∈ [ 4 ] , at most ( ∣ V 3 ∖ V 3 ′ ∣ + ∣ V 4 ∖ V 4 ′ ∣ ) r ≤ 4 η r 2 (|V_3\setminus V_3'|+|V_4\setminus V_4'|)r\le4\eta r^2 ( ∣ V 3 ∖ V 3 ′ ∣ + ∣ V 4 ∖ V 4 ′ ∣ ) r ≤ 4 η r 2 of these paths contain an internal vertex outside V 3 ′ ∪ V 4 ′ V_3'\cup V_4' V 3 ′ ∪ V 4 ′ . Next, since x , y ∉ B 1 ∪ B 2 x,y\notin B_1\cup B_2 x , y ∈ / B 1 ∪ B 2 , each of them is incident with at most η r \eta r η r edges of E \mathcal{E} E . Hence, at most 2 η r 2 2\eta r^2 2 η r 2 paths have their first or last edge in E \mathcal{E} E . Finally, since x x x and y y y are fixed, each edge between V 3 V_3 V 3 and V 4 V_4 V 4 can be the second edge of at most one ( x , y ) (x,y) ( x , y ) -path of length 3. Thus, there are at most ∣ E ∣ ≤ η 2 r 2 |\mathcal{E}|\le\eta^2r^2 ∣ E ∣ ≤ η 2 r 2 such paths. Therefore, the number of good balanced ( x , y ) (x,y) ( x , y ) -paths is at least ∣ P x y ∣ − 4 η r 2 − 2 η r 2 − η 2 r 2 ≥ ( 1 / 2 − 10 η ) r 2 ≥ r 2 / 4 |\mathcal{P}_{xy}|-4\eta r^2-2\eta r^2-\eta^2r^2\ge(1/2-10\eta)r^2\ge r^2/4 ∣ P x y ∣ − 4 η r 2 − 2 η r 2 − η 2 r 2 ≥ ( 1/2 − 10 η ) r 2 ≥ r 2 /4 . ■
:::
Next, we find a good 4 4 4 -cycle in G [ V 1 ′ ∪ V 2 ′ ] G[V_1'\cup V_2'] G [ V 1 ′ ∪ V 2 ′ ] . For v , v ′ ∈ V 1 ′ v,v'\in V_1' v , v ′ ∈ V 1 ′ , let p v v ′ p_{vv'} p v v ′ denote the number of ( v , v ′ ) (v,v') ( v , v ′ ) -paths of length 2 2 2 with their internal vertex in V 2 ′ V_2' V 2 ′ . Hence, by (3) , we have
∑ v , v ′ ∈ V 1 ′ p v v ′ = ∑ u ∈ V 2 ′ d + ( u , V 1 ′ ) d − ( u , V 1 ′ ) ≥ ( 1 4 − 4 η ) r 3 (4) \sum_{v,v'\in V_1'}p_{vv'}=\sum_{u\in V_2'}d^{+}(u,V_1')d^{-}(u,V_1')\ge\left(\frac{1}{4}-4\eta\right)r^3 \tag*{(4)} v , v ′ ∈ V 1 ′ ∑ p v v ′ = u ∈ V 2 ′ ∑ d + ( u , V 1 ′ ) d − ( u , V 1 ′ ) ≥ ( 4 1 − 4 η ) r 3 (4)
and ∣ p v v ′ − p v ′ v ∣ = ∣ d + ( v , V 2 ′ ) − d + ( v ′ , V 2 ′ ) ∣ ≤ 4 η r |p_{vv'}-p_{v'v}|=|d^+(v,V'_2)-d^+(v',V'_2)|\le4\eta r ∣ p v v ′ − p v ′ v ∣ = ∣ d + ( v , V 2 ′ ) − d + ( v ′ , V 2 ′ ) ∣ ≤ 4 η r . Consequently, by (4), the number of 4-cycles satisfies
∑ v , v ′ ∈ V 1 ′ p v v ′ p v ′ v / 2 ≥ ∑ v , v ′ ∈ V 1 ′ p v v ′ 2 / 2 − 2 η r ∑ v , v ′ ∈ V 1 ′ p v v ′ ≥ ( ∑ v , v ′ ∈ V 1 ′ p v v ′ ) 2 2 r 2 − 2 η r 4 ≥ ( 1 32 − 3 η ) r 4 \sum_{v,v'\in V'_1}p_{vv'}p_{v'v}/2\ge\sum_{v,v'\in V'_1}p_{vv'}^2/2-2\eta r\sum_{v,v'\in V'_1}p_{vv'}\ge\frac{\left(\sum_{v,v'\in V'_1}p_{vv'}\right)^2}{2r^2}-2\eta r^4\ge\left(\frac{1}{32}-3\eta\right)r^4 v , v ′ ∈ V 1 ′ ∑ p v v ′ p v ′ v /2 ≥ v , v ′ ∈ V 1 ′ ∑ p v v ′ 2 /2 − 2 η r v , v ′ ∈ V 1 ′ ∑ p v v ′ ≥ 2 r 2 ( ∑ v , v ′ ∈ V 1 ′ p v v ′ ) 2 − 2 η r 4 ≥ ( 32 1 − 3 η ) r 4
After excluding at most ∣ E ∣ r 2 |\mathcal{E}|r^2 ∣ E ∣ r 2 cycles with at least one edge in E \mathcal{E} E , we obtain a good 4-cycle in G [ V 1 ′ ∪ V 2 ′ ] G[V'_1\cup V'_2] G [ V 1 ′ ∪ V 2 ′ ] with 2 vertices in V 1 ′ V'_1 V 1 ′ and the remaining vertices in V 2 ′ V'_2 V 2 ′ , since ( 1 / 32 − 3 η ) r 4 − ∣ E ∣ r 2 > 0 (1/32-3\eta)r^4-|\mathcal{E}|r^2>0 ( 1/32 − 3 η ) r 4 − ∣ E ∣ r 2 > 0 .
We now extend a good 4-cycle in G [ V 1 ′ ∪ V 2 ′ ] G[V'_1\cup V'_2] G [ V 1 ′ ∪ V 2 ′ ] to a good k k k -balanced cycle. Here, to extend an edge v i v j v_iv_j v i v j between two partite classes means to replace it with a ( v i , v j ) (v_i,v_j) ( v i , v j ) -path of length 3 whose internal vertices lie in the other two classes, one in each. Starting from a good 4-cycle in G [ V 1 ′ ∪ V 2 ′ ] G[V'_1\cup V'_2] G [ V 1 ′ ∪ V 2 ′ ] , we extend two vertex-disjoint edges, regardless of their orientations, to obtain a good 2-balanced cycle containing exactly two edges between V 1 ′ V'_1 V 1 ′ and V 2 ′ V'_2 V 2 ′ and two between V 3 ′ V'_3 V 3 ′ and V 4 ′ V'_4 V 4 ′ . Now suppose that 2 ≤ j < k 2\le j<k 2 ≤ j < k and we have a good j j j -balanced cycle with the same property. Extending an edge between V 1 ′ V'_1 V 1 ′ and V 2 ′ V'_2 V 2 ′ creates a new edge between V 3 ′ V'_3 V 3 ′ and V 4 ′ V'_4 V 4 ′ , and vice versa. Thus, after extending one edge between V 1 ′ V'_1 V 1 ′ and V 2 ′ V'_2 V 2 ′ and one edge between V 3 ′ V'_3 V 3 ′ and V 4 ′ V'_4 V 4 ′ , we obtain a good ( j + 1 ) (j+1) ( j + 1 ) -balanced cycle with the same property. By Claim 3.7 , these extensions can be performed greedily while avoiding all previously used vertices, since at each step there are at least r 2 4 − 4 K r ≥ r 2 8 > 0 \frac{r^2}{4}-4Kr\ge\frac{r^2}{8}>0 4 r 2 − 4 K r ≥ 8 r 2 > 0 available replacement paths. This yields a good k k k -balanced cycle for every 2 ≤ k ≤ K 2\le k\le K 2 ≤ k ≤ K .
Let N N N be the constant given by Lemma 3.3 . There are only finitely many pairs ( c , k ) (c,k) ( c , k ) satisfying c k ≤ N ck\le N c k ≤ N . Let r 0 ∗ r_0^* r 0 ∗ be the maximum of all the r 0 r_0 r 0 provided by Lemmas 3.4 and 3.5 over all such pairs. Combining Lemmas 3.3 to 3.5 completes the proof of Theorem 1.4 for c ≥ 4 c\ge4 c ≥ 4 .
Balanced cycles in regular tripartite tournaments
The extremal family
We use the following extremal family of regular tripartite tournaments which are not robust outexpanders introduced in [4 ] .
Definition 4.1 ([4 ] ). For β ∈ [ 0 , 1 / 2 ] \beta\in[0,1/2] β ∈ [ 0 , 1/2 ] , r ∈ N r\in\mathbb{N} r ∈ N , and disjoint vertex sets A = A ^ ∪ A ˇ A=\hat{A}\cup\check{A} A = A ^ ∪ A ˇ , B B B and C C C satisfying ∣ A ∣ = ∣ B ∣ = ∣ C ∣ = r |A|=|B|=|C|=r ∣ A ∣ = ∣ B ∣ = ∣ C ∣ = r , ∣ A ^ ∣ = ( 1 − β ) r |\hat{A}|=(1-\beta)r ∣ A ^ ∣ = ( 1 − β ) r and ∣ A ˇ ∣ = β r |\check{A}|=\beta r ∣ A ˇ ∣ = β r , let G β ( A ^ , A ˇ , B , C ) G_\beta(\hat{A},\check{A},B,C) G β ( A ^ , A ˇ , B , C ) be the family of tripartite tournaments on A ∪ B ∪ C A\cup B\cup C A ∪ B ∪ C with edge set E ( C , A ^ ) ∪ E ( A ^ , B ) ∪ E ( B , A ˇ ) ∪ E ( A ˇ , C ) E(C,\hat{A})\cup E(\hat{A},B)\cup E(B,\check{A})\cup E(\check{A},C) E ( C , A ^ ) ∪ E ( A ^ , B ) ∪ E ( B , A ˇ ) ∪ E ( A ˇ , C ) together with a β r \beta r β r -regular graph oriented from C C C to B B B and its complement (which has to be ( 1 − β ) r (1-\beta)r ( 1 − β ) r -regular) oriented from B B B to C C C .
The extremal family G β G_\beta G β is illustrated in Figure 1 a. In particular, when β = 0 \beta=0 β = 0 , it reduces to the cyclic tripartite tournament G 0 G_0 G 0 , with C → A → B → C C\to A\to B\to C C → A → B → C , as shown in Figure 1 b.
Figure 1. Extremal regular tripartite tournaments: the family G β \mathcal{G}_{\beta} G β and cyclic extremal tournament G 0 G_0 G 0 .
For two regular tripartite tournaments G 1 G_1 G 1 and G 2 G_2 G 2 with the same partition V = V 1 ∪ V 2 ∪ V 3 V=V_1\cup V_2\cup V_3 V = V 1 ∪ V 2 ∪ V 3 , where ∣ V i ∣ = r |V_i|=r ∣ V i ∣ = r for each i ∈ [ 3 ] i\in[3] i ∈ [ 3 ] , define dist ( G 1 , G 2 ) : = 1 2 ∣ E ( G 1 ) △ E ( G 2 ) ∣ \operatorname{dist}(G_1,G_2):=\frac{1}{2}|E(G_1)\mathbin{\triangle}E(G_2)| dist ( G 1 , G 2 ) := 2 1 ∣ E ( G 1 ) △ E ( G 2 ) ∣ . We say that G 1 G_1 G 1 and G 2 G_2 G 2 are ε \varepsilon ε -close if ∣ E ( G 1 ) △ E ( G 2 ) ∣ ≤ ε ∣ V ∣ 2 |E(G_1)\mathbin{\triangle}E(G_2)|\le\varepsilon|V|^2 ∣ E ( G 1 ) △ E ( G 2 ) ∣ ≤ ε ∣ V ∣ 2 . Moreover, G G G is said to be ε \varepsilon ε -close to G β G_\beta G β if there exists G ∗ ∈ G β G^*\in\mathcal{G}_\beta G ∗ ∈ G β that is ε \varepsilon ε -close to G G G . For γ > 0 \gamma>0 γ > 0 , let U γ ( G 1 ; G 2 ) : = { v ∈ V : d G 1 ∖ G 2 + ( v ) + d G 1 ∖ G 2 + ( v ) ≥ γ ∣ V ∣ } U_\gamma(G_1;G_2):=\{v\in V:d^+_{G_1\setminus G_2}(v)+d^+_{G_1\setminus G_2}(v)\ge\gamma|V|\} U γ ( G 1 ; G 2 ) := { v ∈ V : d G 1 ∖ G 2 + ( v ) + d G 1 ∖ G 2 + ( v ) ≥ γ ∣ V ∣ } and we will often write U γ U_\gamma U γ in place of U γ ( G 1 ; G 2 ) U_\gamma(G_1;G_2) U γ ( G 1 ; G 2 ) . When G 1 G_1 G 1 and G 2 G_2 G 2 are clear from the context, we abbreviate U γ ( G 1 ; G 2 ) U_\gamma(G_1;G_2) U γ ( G 1 ; G 2 ) to U γ U_\gamma U γ . The following bound is immediate.
Fact 4.2. Suppose that G 1 G_1 G 1 and G 2 G_2 G 2 are ε \varepsilon ε -close. Then ∣ U γ ( G 1 , G 2 ) ∣ ≤ 3 ε r / γ |U_\gamma(G_1,G_2)|\le3\varepsilon r/\gamma ∣ U γ ( G 1 , G 2 ) ∣ ≤ 3 ε r / γ .
Proof. Since 2 ∣ E ( G 1 ) ∖ E ( G 2 ) ∣ = ∣ E ( G 1 ) △ E ( G 2 ) ∣ 2|E(G_1) \setminus E(G_2)| = |E(G_1)\triangle E(G_2)| 2∣ E ( G 1 ) ∖ E ( G 2 ) ∣ = ∣ E ( G 1 ) △ E ( G 2 ) ∣ , we have
∣ U γ ( G 1 ; G 2 ) ∣ ⋅ γ ∣ V ∣ ≤ ∑ v ∈ U γ ( G 1 , G 2 ) d G 1 ∖ G 2 ( v ) ≤ 2 ∣ E ( G 1 ) ∖ E ( G 2 ) ∣ ≤ ε ∣ V ∣ 2 . |U_{\gamma}(G_1;G_2)| \cdot\gamma|V| \le\sum_{v\in U_{\gamma}(G_1,G_2)} d_{G_1\setminus G_2}(v) \le2|E(G_1) \setminus E(G_2)| \le\varepsilon|V|^2. ∣ U γ ( G 1 ; G 2 ) ∣ ⋅ γ ∣ V ∣ ≤ v ∈ U γ ( G 1 , G 2 ) ∑ d G 1 ∖ G 2 ( v ) ≤ 2∣ E ( G 1 ) ∖ E ( G 2 ) ∣ ≤ ε ∣ V ∣ 2 .
Therefore ∣ U ∣ ≤ 3 ε r / γ |U| \le3\varepsilon r/\gamma ∣ U ∣ ≤ 3 ε r / γ . □
We use the stability theorem of Di Braccio et al. [4 ] in the following form.
Theorem 4.3 (Di Braccio et al. [4 ] ). Let 0 < ν ≪ τ ≪ ε ≪ 1 0 < \nu\ll\tau\ll\varepsilon\ll1 0 < ν ≪ τ ≪ ε ≪ 1 . Then there exists an integer r 0 r_0 r 0 such that every regular tripartite tournament with common partite size r ≥ r 0 r \ge r_0 r ≥ r 0 is either a robust ( ν , τ ) (\nu,\tau) ( ν , τ ) -outexpander or ε \varepsilon ε -close to G β \mathcal{G}_{\beta} G β for some β ∈ [ 0 , 1 / 2 ] \beta\in[0,1/2] β ∈ [ 0 , 1/2 ] .
The next two lemmas handle the two alternatives in Theorem 4.3 . The robust outexpander case is treated in Lemma 4.7 , while the case in which G G G is ε \varepsilon ε -close to G β \mathcal{G}_{\beta} G β is treated in Lemma 4.8 . Together, they establish Theorem 1.4 for c = 3 c = 3 c = 3 .
Linear forests
For later use, we combine weaker versions of Lemmas 4.11 and 4.12 of Di Braccio et al. [4 ] into a single lemma. Those results provide linear many edge-disjoint forests, here we need only one.
Lemma 4.4 (Di Braccio et al. [4 ] ). Let 0 < 1 / r ≪ ε ≪ γ ≪ 1 0 < 1/r \ll\varepsilon\ll\gamma\ll1 0 < 1/ r ≪ ε ≪ γ ≪ 1 . Suppose that G G G is a regular tripartite tournament with partite classes A A A , B B B , C C C , each of size r r r , and that G G G is ε \varepsilon ε -close to G ′ ∈ G β ( A ^ , A ˘ , B , C ) G' \in\mathcal{G}_{\beta}(\widehat{A}, \breve{A}, B, C) G ′ ∈ G β ( A , A ˘ , B , C ) , where A = A ^ ∪ A ˘ A = \widehat{A} \cup\breve{A} A = A ∪ A ˘ and either β = 0 \beta= 0 β = 0 or γ ≪ β ≤ 1 / 2 \gamma\ll\beta\le1/2 γ ≪ β ≤ 1/2 . Then G G G contains a linear forest F F F such that e ( F ) ≤ γ r e(F) \le\gamma r e ( F ) ≤ γ r and d F + ( v ) = d F − ( v ) = 1 d_F^+(v) = d_F^-(v) = 1 d F + ( v ) = d F − ( v ) = 1 for every v ∈ U γ ( G , G ′ ) v \in U_{\gamma}(G,G') v ∈ U γ ( G , G ′ ) .
Moreover, the following hold:
(i) If β = 0 \beta= 0 β = 0 , then e F ( C , B ) = e F ( B , A ) = e F ( A , C ) e_F(C,B) = e_F(B,A) = e_F(A,C) e F ( C , B ) = e F ( B , A ) = e F ( A , C ) .
(ii) If β > 0 \beta> 0 β > 0 , then e F ( C , A ) = e F ( A , B ) e_F(C,A) = e_F(A,B) e F ( C , A ) = e F ( A , B ) and e F ( B , A ) = e F ( A , C ) e_F(B,A) = e_F(A,C) e F ( B , A ) = e F ( A , C ) . Moreover, each path in F F F is a ( C , B ) (C,B) ( C , B ) -path.
We also use two results on Hamilton cycles from the same paper.
Lemma 4.5 (Di Braccio et al. [4 ] ). Let 1 / n ≪ η ≪ 1 1/n \ll\eta\ll1 1/ n ≪ η ≪ 1 . Let G G G be a tripartite digraph with partite classes A A A , B B B , C C C such that ( 1 − η ) n ≤ ∣ A ∣ ≤ n (1-\eta)n \le|A| \le n ( 1 − η ) n ≤ ∣ A ∣ ≤ n and ∣ B ∣ = ∣ C ∣ = n |B| = |C| = n ∣ B ∣ = ∣ C ∣ = n . Suppose every vertex has at least ( 1 − η ) n (1-\eta)n ( 1 − η ) n outneighbors in the next part and at least ( 1 − η ) n (1-\eta)n ( 1 − η ) n inneighbors in the previous part with respect to C → A → B → C C \to A \to B \to C C → A → B → C . Then every matching M ⊆ E G ( C , B ) M \subseteq E_G(C,B) M ⊆ E G ( C , B ) of size exactly n − ∣ A ∣ n - |A| n − ∣ A ∣ is contained in a Hamilton cycle of G G G .
Lemma 4.6 (Di Braccio et al. [4 ] ). Let 1 / n ≪ η ≪ 1 1/n \ll\eta\ll1 1/ n ≪ η ≪ 1 . Let G G G be a four-partite digraph with partition V ( G ) = X ∪ Y ∪ B ∪ C V(G)=X\cup Y\cup B\cup C V ( G ) = X ∪ Y ∪ B ∪ C , where ∣ B ∣ = ∣ C ∣ = n |B|=|C|=n ∣ B ∣ = ∣ C ∣ = n and ∣ X ∣ , ∣ Y ∣ ≤ ( 1 − 8 η ) n |X|,|Y|\le(1-8\eta)n ∣ X ∣ , ∣ Y ∣ ≤ ( 1 − 8 η ) n . Suppose
d G + ( x , B ) , d G − ( x , C ) ≥ ( 1 − η ) n ( x ∈ X ) , d_G^{+}(x,B),d_G^{-}(x,C)\ge(1-\eta)n \qquad(x\in X), d G + ( x , B ) , d G − ( x , C ) ≥ ( 1 − η ) n ( x ∈ X ) , d G + ( y , C ) , d G − ( y , B ) ≥ ( 1 − η ) n ( y ∈ Y ) , d_G^{+}(y,C),d_G^{-}(y,B)\ge(1-\eta)n \qquad(y\in Y), d G + ( y , C ) , d G − ( y , B ) ≥ ( 1 − η ) n ( y ∈ Y ) , d G + ( b , Y ∪ C ) , d G − ( b , X ∪ C ) ≥ ( 1 − η ) n ( b ∈ B ) , d_G^{+}(b,Y\cup C),d_G^{-}(b,X\cup C)\ge(1-\eta)n \qquad(b\in B), d G + ( b , Y ∪ C ) , d G − ( b , X ∪ C ) ≥ ( 1 − η ) n ( b ∈ B ) , d G + ( c , X ∪ B ) , d G − ( c , Y ∪ B ) ≥ ( 1 − η ) n ( c ∈ C ) . d_G^{+}(c,X\cup B),d_G^{-}(c,Y\cup B)\ge(1-\eta)n \qquad(c\in C). d G + ( c , X ∪ B ) , d G − ( c , Y ∪ B ) ≥ ( 1 − η ) n ( c ∈ C ) . Then every matching M ⊆ E G ( C , B ) M\subseteq E_G(C,B) M ⊆ E G ( C , B ) with ∣ M ∣ ≤ η n |M|\le\eta n ∣ M ∣ ≤ η n is contained in a Hamilton cycle of G G G .
Non-extremal case
Lemma 4.7. Let 0 < ν ≤ τ ≪ 1 0<\nu\le\tau\ll1 0 < ν ≤ τ ≪ 1 . There exists an integer r 0 r_0 r 0 such that every regular tripartite tournament G G G with partite classes A , B , C A,B,C A , B , C of common size r ≥ r 0 r\ge r_0 r ≥ r 0 which is a robust ( ν , τ ) (\nu,\tau) ( ν , τ ) -outexpander contains a k k k -balanced cycle for every integer 1 ≤ k ≤ r 1\le k\le r 1 ≤ k ≤ r .
Proof. Let A = V 1 A=V_1 A = V 1 , B = V 2 B=V_2 B = V 2 , C = V 3 C=V_3 C = V 3 . Choose constants satisfying
0 < 1 / r 0 ≪ ξ ≪ ν ′ ≪ 1 / M ≪ 1 / M ′ ≪ ε ≪ d , ν , τ ≪ 1. 0<1/r_0\ll\xi\ll\nu'\ll1/M\ll1/M'\ll\varepsilon\ll d,\nu,\tau\ll1. 0 < 1/ r 0 ≪ ξ ≪ ν ′ ≪ 1/ M ≪ 1/ M ′ ≪ ε ≪ d , ν , τ ≪ 1.
Case 1. k ≤ ξ r k\le\xi r k ≤ ξ r
By Proposition 3.1 , G G G contains at least r 3 / 4 r^3/4 r 3 /4 triangles. Relabeling the classes if necessary, we may assume that at least r 3 / 8 r^3/8 r 3 /8 of them have orientation A → B → C → A A\to B\to C\to A A → B → C → A . Let H H H be the undirected tripartite graph with V ( H ) = V ( G ) V(H)=V(G) V ( H ) = V ( G ) and E ( H ) = E G ( A , B ) ∪ E G ( B , C ) ∪ E G ( C , A ) E(H)=E_G(A,B)\cup E_G(B,C)\cup E_G(C,A) E ( H ) = E G ( A , B ) ∪ E G ( B , C ) ∪ E G ( C , A ) . Thus H H H contains at least r 3 / 8 r^3/8 r 3 /8 triangles.
We apply Lemma 2.7 to H H H with parameters ( ε , d , M ′ ) (\varepsilon,d,M') ( ε , d , M ′ ) and partite classes A , B , C A,B,C A , B , C , obtaining a spanning subgraph H ′ H' H ′ , an exceptional set V 0 V_0 V 0 with ∣ V 0 ∣ ≤ ε n |V_0|\le\varepsilon n ∣ V 0 ∣ ≤ ε n , and 3 t 3t 3 t clusters A 1 , … , A t , B 1 , … , B t , C 1 , … , C t A_1,\ldots,A_t,B_1,\ldots,B_t,C_1,\ldots,C_t A 1 , … , A t , B 1 , … , B t , C 1 , … , C t of equal size m m m , where M ′ ≤ t ≤ M M'\le t\le M M ′ ≤ t ≤ M . Let R R R be the corresponding reduced graph with parameters ( ε , d ) (\varepsilon,d) ( ε , d ) . By Lemma 2.7 (iii),
e ( H ) − e ( H ′ ) = 1 2 ∑ x ∈ V ( H ) ( d H ( x ) − d H ′ ( x ) ) ≤ 1 2 ( d + ε ) n 2 . e(H)-e(H')=\frac{1}{2}\sum_{x\in V(H)}(d_H(x)-d_{H'}(x))\le\frac{1}{2}(d+\varepsilon)n^2. e ( H ) − e ( H ′ ) = 2 1 x ∈ V ( H ) ∑ ( d H ( x ) − d H ′ ( x )) ≤ 2 1 ( d + ε ) n 2 .
Each deleted edge belongs to at most r r r triangles, and each exceptional vertex belongs to at most r 2 r^2 r 2 triangles. Hence H ′ − V 0 H'-V_0 H ′ − V 0 contains at least
r 3 8 − 1 2 ( d + ε ) n 2 r − ε n r 2 = ( 1 8 − 9 2 d − 15 2 ε ) r 3 > 0 \frac{r^3}{8}-\frac{1}{2}(d+\varepsilon)n^2r-\varepsilon nr^2=\left(\frac{1}{8}-\frac{9}{2}d-\frac{15}{2}\varepsilon\right)r^3>0 8 r 3 − 2 1 ( d + ε ) n 2 r − ε n r 2 = ( 8 1 − 2 9 d − 2 15 ε ) r 3 > 0
triangles. Therefore R R R contains a triangle T T T . We may assume that its vertices are V 11 , V 21 , V 31 V_{11},V_{21},V_{31} V 11 , V 21 , V 31 .
Applying Lemma 2.9 to the triangle T T T with Δ = 2 \Delta=2 Δ = 2 , we obtain a subgraph H T H_T H T of H ′ H' H ′ . More precisely, V ( H T ) = V 11 ′ ∪ V 21 ′ ∪ V 31 ′ V(H_T)=V'_{11}\cup V'_{21}\cup V'_{31} V ( H T ) = V 11 ′ ∪ V 21 ′ ∪ V 31 ′ , where each V i 1 ′ ⊆ V i 1 V'_{i1}\subseteq V_{i1} V i 1 ′ ⊆ V i 1 is obtained by deleting exactly 2 ε m 2\varepsilon m 2 ε m vertices. As t ≤ M t\le M t ≤ M and t m ≥ ( 1 − ε ) r tm\ge(1-\varepsilon)r t m ≥ ( 1 − ε ) r , we have ∣ V i 1 ′ ∣ ≥ ( 1 − 2 ε ) ( 1 − ε ) r / M ≥ ξ r ≥ k |V'_{i1}|\ge(1-2\varepsilon)(1-\varepsilon)r/M\ge\xi r\ge k ∣ V i 1 ′ ∣ ≥ ( 1 − 2 ε ) ( 1 − ε ) r / M ≥ ξ r ≥ k . Furthermore, the three unordered pairs ( V i 1 ′ , V j 1 ′ ) (V'_{i1},V'_{j1}) ( V i 1 ′ , V j 1 ′ ) are all ( ε , d − 3 ε ) (\sqrt{\varepsilon},d-3\varepsilon) ( ε , d − 3 ε ) -super-regular. By Lemma 2.8 , one can embed a k k k -balanced cycle into H ′ H' H ′ . By the definition of H H H , this corresponds to a k k k -balanced cycle in G G G .
Case 2. k > ξ r k>\xi r k > ξ r
Independently for each i ∈ [ 3 ] i\in[3] i ∈ [ 3 ] , choose a k k k -subset U i U_i U i of V i V_i V i uniformly at random, and let U = U 1 ∪ U 2 ∪ U 3 U=U_1\cup U_2\cup U_3 U = U 1 ∪ U 2 ∪ U 3 . Consider the 3 k 3k 3 k -subsets S S S of V ( G ) V(G) V ( G ) for which G [ S ] G[S] G [ S ] is not a robust ( ν ′ , 4 τ ) (\nu',4\tau) ( ν ′ , 4 τ ) -outexpander. Since δ 0 ( G ) = r = ∣ V ( G ) ∣ / 3 \delta^0(G)=r=|V(G)|/3 δ 0 ( G ) = r = ∣ V ( G ) ∣/3 , Lemma 2.11 and Proposition 2.15 imply that the number of such sets S S S is at most
1 9 r 2 ( 3 r 3 k ) ≤ 1 9 r 2 ∑ 0 ≤ a , b , c ≤ r a + b + c = 3 k ( r a ) ( r b ) ( r c ) ≤ ( r + 1 ) 2 9 r 2 ( r k ) 3 (5) \frac{1}{9r^2}\binom{3r}{3k}\le\frac{1}{9r^2}\sum_{\substack{0\le a,b,c\le r\\a+b+c=3k}}\binom{r}{a}\binom{r}{b}\binom{r}{c}\le\frac{(r+1)^2}{9r^2}\binom{r}{k}^{3} \tag*{(5)} 9 r 2 1 ( 3 k 3 r ) ≤ 9 r 2 1 0 ≤ a , b , c ≤ r a + b + c = 3 k ∑ ( a r ) ( b r ) ( c r ) ≤ 9 r 2 ( r + 1 ) 2 ( k r ) 3 (5)
@ unerquicklich Since there are exactly ( r k ) 3 \binom{r}{k}^{3} ( k r ) 3 choices for U U U , it follows that
P ( G [ U ] is not a robust ( ν ′ , 4 τ ) -outexpander ) ≤ ( r + 1 ) 2 9 r 2 ≤ 1 4 . \mathbb{P}(G[U]\text{ is not a robust }(\nu',4\tau)\text{-outexpander}) \le\frac{(r+1)^{2}}{9r^{2}} \le\frac{1}{4}. P ( G [ U ] is not a robust ( ν ′ , 4 τ ) -outexpander ) ≤ 9 r 2 ( r + 1 ) 2 ≤ 4 1 .
For each fixed v ∈ V i v \in V_i v ∈ V i , we have E [ d G ± ( v , U ) ] = k r ∑ j ∈ [ 3 ] ∖ { i } d G ± ( v , V j ) = k \mathbb{E}[d_G^{\pm}(v,U)] = \frac{k}{r}\sum_{j\in[3]\setminus\{i\}}d_G^{\pm}(v,V_j)=k E [ d G ± ( v , U )] = r k ∑ j ∈ [ 3 ] ∖ { i } d G ± ( v , V j ) = k . By Lemma 2.13 and the union bound, P ( δ 0 ( G [ U ] ) < 3 k / 4 ) ≤ 4 ⋅ 3 r e − k / 16 < 1 / 4 \mathbb{P}(\delta^{0}(G[U])<3k/4)\leq4\cdot3re^{-k/16}<1/4 P ( δ 0 ( G [ U ]) < 3 k /4 ) ≤ 4 ⋅ 3 r e − k /16 < 1/4 . Consequently, there exists a 3 k 3k 3 k -set U U U such that G [ U ] G[U] G [ U ] is a robust ( ν ′ , 4 τ ) (\nu',4\tau) ( ν ′ , 4 τ ) -outexpander and δ 0 ( G [ U ] ) ≥ 3 k 4 = ∣ U ∣ 4 \delta^{0}(G[U])\geq\frac{3k}{4}=\frac{|U|}{4} δ 0 ( G [ U ]) ≥ 4 3 k = 4 ∣ U ∣ .
Since ν ′ ≤ 4 τ < 1 / 64 \nu'\leq4\tau<1/64 ν ′ ≤ 4 τ < 1/64 , Lemma 2.12 gives a Hamilton cycle in G [ U ] G[U] G [ U ] . This cycle contains exactly k k k vertices from each V i V_i V i and is therefore k k k -balanced.
The extremal case
Lemma 4.8. There exists ε > 0 \varepsilon>0 ε > 0 such that, for all sufficiently large r r r , every regular tripartite tournament G G G which is ε \varepsilon ε -close to G β G_\beta G β for some 0 ≤ β ≤ 1 / 2 0\leq\beta\leq1/2 0 ≤ β ≤ 1/2 contains a k k k -balanced cycle for every 1 ≤ k ≤ r 1\leq k\leq r 1 ≤ k ≤ r .
Proof. Choose constants satisfying
1 / r ≪ ε ≪ γ ≪ λ ≪ η ≪ σ ≪ τ ≪ 1. (6) 1/r\ll\varepsilon\ll\gamma\ll\lambda\ll\eta\ll\sigma\ll\tau\ll1. \tag*{(6)} 1/ r ≪ ε ≪ γ ≪ λ ≪ η ≪ σ ≪ τ ≪ 1. (6) Let G 0 G_0 G 0 be the cyclic extremal tournament with A → B → C → A A\to B\to C\to A A → B → C → A . Choose G 1 ∈ G β ( A ^ , A ˘ , B , C ) G_1\in G_\beta(\widehat A,\breve A,B,C) G 1 ∈ G β ( A , A ˘ , B , C ) such that dist ( G , G 1 ) ≤ 9 ε r 2 / 2 \operatorname{dist}(G,G_1)\leq9\varepsilon r^{2}/2 dist ( G , G 1 ) ≤ 9 ε r 2 /2 . Let d = β r d=\beta r d = β r and q = ( 1 − β ) r q=(1-\beta)r q = ( 1 − β ) r .
Case 1. k ≤ ( 1 − λ ) r k\leq(1-\lambda)r k ≤ ( 1 − λ ) r .
Let U = U γ ( G , G 1 ) U=U_\gamma(G,G_1) U = U γ ( G , G 1 ) . For each V ∈ { A ^ , A ˘ , B , C ˘ } V\in\{\widehat A,\breve A,B,\breve C\} V ∈ { A , A ˘ , B , C ˘ } , write V 0 = V ∖ U V_0=V\setminus U V 0 = V ∖ U . By (5) and Fact 4.2 for every b ∈ B 0 b\in B_0 b ∈ B 0 and c ∈ C 0 c\in C_0 c ∈ C 0 , the following hold
d G + ( b , C 0 ) , d G − ( c , B 0 ) ≥ q − 3 γ r − ∣ U ∣ ≥ q − λ r / 20 > 0 and (7) d_G^{+}(b,C_0),d_G^{-}(c,B_0)\geq q-3\gamma r-|U|\geq q-\lambda r/20>0 \qquad\text{and} \tag*{(7)} d G + ( b , C 0 ) , d G − ( c , B 0 ) ≥ q − 3 γ r − ∣ U ∣ ≥ q − λ r /20 > 0 and (7) d G − ( b , C 0 ) , d G + ( c , B 0 ) ≥ d − 3 γ r − ∣ U ∣ ≥ d − λ r / 20. (8) d_G^{-}(b,C_0),d_G^{+}(c,B_0)\geq d-3\gamma r-|U|\geq d-\lambda r/20. \tag*{(8)} d G − ( b , C 0 ) , d G + ( c , B 0 ) ≥ d − 3 γ r − ∣ U ∣ ≥ d − λ r /20. (8) If q − λ r / 20 < k q-\lambda r/20<k q − λ r /20 < k , then d − λ r / 20 > 0 d-\lambda r/20>0 d − λ r /20 > 0 . By (6) and (7), there exist c ∈ C 0 c\in C_0 c ∈ C 0 and b 1 , b 2 ∈ B 0 b_1,b_2\in B_0 b 1 , b 2 ∈ B 0 such that b 1 c , c b 2 ∈ E ( G ) b_1c,cb_2\in E(G) b 1 c , c b 2 ∈ E ( G ) . Consider disjoint subsets B 1 , B 2 B_1,B_2 B 1 , B 2 of B 0 B_0 B 0 containing b 1 , b 2 b_1,b_2 b 1 , b 2 , respectively, with ∣ B 1 ∣ = q − λ r / 20 |B_1|=q-\lambda r/20 ∣ B 1 ∣ = q − λ r /20 and ∣ B 2 ∣ = k − q + λ r / 20 ≤ d − λ r / 20 |B_2|=k-q+\lambda r/20\leq d-\lambda r/20 ∣ B 2 ∣ = k − q + λ r /20 ≤ d − λ r /20 . By Hall’s theorem, we obtain matchings M 1 = M [ B 1 , C 1 ] M_1=M[B_1,C_1] M 1 = M [ B 1 , C 1 ] and M 2 = M [ C 2 , B 2 ] M_2=M[C_2,B_2] M 2 = M [ C 2 , B 2 ] containing b 1 c , c b 2 b_1c,cb_2 b 1 c , c b 2 , respectively. By construction, the matchings M 1 M_1 M 1 and M 2 M_2 M 2 both contain the vertex c c c . Let C 1 ∩ C 2 = { v 1 , … , v t } C_1\cap C_2=\{v_1,\ldots,v_t\} C 1 ∩ C 2 = { v 1 , … , v t } . Since ∣ C 0 ∣ ≥ k |C_0|\geq k ∣ C 0 ∣ ≥ k and ∣ C 1 ∪ C 2 ∣ = k − t |C_1\cup C_2|=k-t ∣ C 1 ∪ C 2 ∣ = k − t , we may choose distinct vertices u 1 , … , u t ∈ C 0 ∖ ( C 1 ∪ C 2 ) u_1,\ldots,u_t\in C_0\setminus(C_1\cup C_2) u 1 , … , u t ∈ C 0 ∖ ( C 1 ∪ C 2 ) . Distribute the vertices of C 2 ∖ C 1 C_2\setminus C_1 C 2 ∖ C 1 arbitrarily between the pairs v i , u i v_i,u_i v i , u i , and those of C 1 ∖ C 2 C_1\setminus C_2 C 1 ∖ C 2 between the pairs u i , v i + 1 u_i,v_{i+1} u i , v i + 1 , where v t + 1 = v 1 v_{t+1}=v_1 v t + 1 = v 1 . The number and order of vertices placed between each pair are arbitrary. This yields a cyclic ordering π \pi π of the k k k vertices of C 0 C_0 C 0 . Call an ordered pair ( c , c ′ ) (c,c') ( c , c ′ ) of consecutive vertices in this cyclic ordering type I if c ∈ C 2 c\in C_2 c ∈ C 2 , and of type II if c ′ ∈ C 1 c'\in C_1 c ′ ∈ C 1 . By construction, no consecutive ordered pair ( c , c ′ ) (c,c') ( c , c ′ ) in this cyclic ordering π \pi π satisfies c ∈ C 2 c\in C_2 c ∈ C 2 and c ′ ∈ C 1 c'\in C_1 c ′ ∈ C 1 . Thus, the two types are disjoint. Since there are exactly ∣ C 2 ∣ = ∣ B 2 ∣ |C_2|=|B_2| ∣ C 2 ∣ = ∣ B 2 ∣ type I pairs and ∣ C 1 ∣ = ∣ B 1 ∣ |C_1|=|B_1| ∣ C 1 ∣ = ∣ B 1 ∣ type II pairs, and ∣ B 1 ∣ + ∣ B 2 ∣ = k |B_1|+|B_2|=k ∣ B 1 ∣ + ∣ B 2 ∣ = k , they account for all k k k consecutive ordered pairs.
By the definition of G 1 G_1 G 1 , for every b ∈ B 0 b\in B_0 b ∈ B 0 and c ∈ C 0 c\in C_0 c ∈ C 0 , we have
∣ { y ∈ A ^ 0 : b → y → c } ∣ ≥ d − ∣ U ∣ − 6 γ r ≥ d − λ r 20 ≥ ∣ B 2 ∣ , if B 2 ≠ ∅ \left|\{y\in\widehat A_0:b\to y\to c\}\right|\geq d-|U|-6\gamma r\geq d-\frac{\lambda r}{20}\geq|B_2|,\qquad\text{if }B_2\ne\varnothing { y ∈ A 0 : b → y → c } ≥ d − ∣ U ∣ − 6 γ r ≥ d − 20 λ r ≥ ∣ B 2 ∣ , if B 2 = ∅ ∣ { x ∈ A ^ 0 : c → x → b } ∣ ≥ q − ∣ U ∣ − 6 γ r ≥ q − λ r 20 ≥ ∣ B 1 ∣ . (9) \left|\{x\in\widehat A_0:c\to x\to b\}\right|\geq q-|U|-6\gamma r\geq q-\frac{\lambda r}{20}\geq|B_1|. \tag*{(9)} { x ∈ A 0 : c → x → b } ≥ q − ∣ U ∣ − 6 γ r ≥ q − 20 λ r ≥ ∣ B 1 ∣. (9) For each type I pair ( c 1 , c 2 ) (c_1,c_2) ( c 1 , c 2 ) , let b b b be the vertex matched to c 1 c_1 c 1 by M 2 M_2 M 2 . By (8) and Hall’s theorem, we can choose distinct vertices y ∈ A ^ 0 y\in\widehat A_0 y ∈ A 0 to obtain paths c 1 b y c 2 c_1byc_2 c 1 b y c 2 . Similarly, for each
type II pair ( c 3 , c 4 ) (c_3,c_4) ( c 3 , c 4 ) , let b b b be the vertex matched to c 4 c_4 c 4 by M 1 M_1 M 1 . We then choose distinct vertices x ∈ A ^ 0 x \in\hat{A}_0 x ∈ A ^ 0 so as to obtain the paths c 3 x b c 4 c_3xbc_4 c 3 x b c 4 . Replacing all consecutive pairs by these paths gives a k k k -balanced cycle.
If q − λ r / 20 ≥ k q-\lambda r/20 \ge k q − λ r /20 ≥ k . Choose a k k k -subset B 1 ⊆ B 0 B_1 \subseteq B_0 B 1 ⊆ B 0 . As above, there is a matching M 1 = M [ B 1 , C 1 ] M_1=M[B_1,C_1] M 1 = M [ B 1 , C 1 ] of size k k k . Let B 2 = C 2 = ∅ B_2=C_2=\varnothing B 2 = C 2 = ∅ and choose an arbitrary cyclic ordering of C 1 C_1 C 1 . All consecutive pairs are of type II, the same argument as above allows us to replace these pairs with paths, thereby obtaining a k k k -balanced cycle.
Case 2. ( 1 − λ ) r ≤ k ≤ r (1-\lambda)r \le k \le r ( 1 − λ ) r ≤ k ≤ r .
We divide this case into two subcases according to whether β < σ \beta<\sigma β < σ or β ≥ σ \beta\ge\sigma β ≥ σ . Let m = λ r m=\lambda r m = λ r .
Subcase 2.1. β < σ \beta<\sigma β < σ .
Since G 1 G_1 G 1 differs from G 0 G_0 G 0 in exactly 3 β r 2 3\beta r^2 3 β r 2 edges, we have dist ( G , G 0 ) ≤ dist ( G , G 1 ) + dist ( G 1 , G 0 ) ≤ ( 9 2 ε + 3 β ) r 2 ≤ 9 2 σ r 2 \operatorname{dist}(G,G_0)\le\operatorname{dist}(G,G_1)+\operatorname{dist}(G_1,G_0)\le\left(\frac{9}{2}\varepsilon+3\beta\right)r^2\le\frac{9}{2}\sigma r^2 dist ( G , G 0 ) ≤ dist ( G , G 1 ) + dist ( G 1 , G 0 ) ≤ ( 2 9 ε + 3 β ) r 2 ≤ 2 9 σ r 2 . Thus G G G is σ \sigma σ -close to G 0 G_0 G 0 . Since σ ≪ τ \sigma\ll\tau σ ≪ τ , Lemma 4.4(i) gives a linear forest F 0 F_0 F 0 with e ( F 0 ) ≤ τ r e(F_0)\le\tau r e ( F 0 ) ≤ τ r , e F 0 ( C , B ) = e F 0 ( B , A ) = e F 0 ( A , C ) e_{F_0}(C,B)=e_{F_0}(B,A)=e_{F_0}(A,C) e F 0 ( C , B ) = e F 0 ( B , A ) = e F 0 ( A , C ) and
U τ ( G , G 0 ) ⊆ V ˚ ( F 0 ) (10) U_\tau(G,G_0)\subseteq\mathring{V}(F_0) \tag*{(10)} U τ ( G , G 0 ) ⊆ V ˚ ( F 0 ) (10)
Indeed, we can extend each component of F 0 F_0 F 0 to a ( C , B ) (C,B) ( C , B ) -path by adding at most two edges at each end, using edges from E G ( A , B ) E_G(A,B) E G ( A , B ) , E G ( B , C ) E_G(B,C) E G ( B , C ) , or E G ( C , A ) E_G(C,A) E G ( C , A ) . By (10) there are at least ( 1 − 3 τ ) r (1-3\tau)r ( 1 − 3 τ ) r choices of each added edge, greater than ∣ V ( F 0 ) ∣ + 4 e ( F 0 ) ≤ 6 τ r |V(F_0)|+4e(F_0)\le6\tau r ∣ V ( F 0 ) ∣ + 4 e ( F 0 ) ≤ 6 τ r , so the extensions can be made greedily and vertex-disjointly. Let F F F be the resulting forest. Then ∣ V ( F ) ∣ ≤ 6 τ r |V(F)|\le6\tau r ∣ V ( F ) ∣ ≤ 6 τ r . Moreover, the way in which F F F was obtained from F 0 F_0 F 0 gives
e F ( C , B ) = e F ( B , A ) = e F ( A , C ) . (11) e_F(C,B)=e_F(B,A)=e_F(A,C). \tag*{(11)} e F ( C , B ) = e F ( B , A ) = e F ( A , C ) . (11)
Next, we construct a path R = c 0 x 1 b 1 c 1 ⋯ c m x m + 1 b m + 1 R=c_0x_1b_1c_1\cdots c_mx_{m+1}b_{m+1} R = c 0 x 1 b 1 c 1 ⋯ c m x m + 1 b m + 1 that is vertex-disjoint from F F F . Its vertices satisfy c i ∈ C c_i\in C c i ∈ C , x i ∈ A x_i\in A x i ∈ A and b i ∈ B b_i\in B b i ∈ B , and it has the additional property that c 0 x i ∈ E ( G ) c_0x_i\in E(G) c 0 x i ∈ E ( G ) for every i ∈ [ m + 1 ] i\in[m+1] i ∈ [ m + 1 ] . Indeed, by (10) , for every x ∈ A ∖ V ( F ) x\in A\setminus V(F) x ∈ A ∖ V ( F ) , b ∈ B ∖ V ( F ) b\in B\setminus V(F) b ∈ B ∖ V ( F ) and c , c ′ ∈ C ∖ V ( F ) c,c'\in C\setminus V(F) c , c ′ ∈ C ∖ V ( F ) we have
∣ N G + ( c , A ) ∩ N G + ( c ′ , A ) ∣ ≥ r − 6 τ r , d G + ( x , B ) , d G + ( b , C ) ≥ r − 3 τ r . \left|N_G^+(c,A)\cap N_G^+(c',A)\right|\ge r-6\tau r,\qquad d_G^+(x,B),\ d_G^+(b,C)\ge r-3\tau r. N G + ( c , A ) ∩ N G + ( c ′ , A ) ≥ r − 6 τ r , d G + ( x , B ) , d G + ( b , C ) ≥ r − 3 τ r .
Starting with c 0 ∈ C ∖ V ( F ) c_0\in C\setminus V(F) c 0 ∈ C ∖ V ( F ) , we successively choose x i ∈ N G + ( c 0 , A ) ∩ N G + ( c i − 1 , A ) x_i\in N_G^+(c_0,A)\cap N_G^+(c_{i-1},A) x i ∈ N G + ( c 0 , A ) ∩ N G + ( c i − 1 , A ) , b i ∈ N G + ( x i , B ) b_i\in N_G^+(x_i,B) b i ∈ N G + ( x i , B ) , and, if i ≤ m i\le m i ≤ m , c i ∈ N G + ( b i , C ) c_i\in N_G^+(b_i,C) c i ∈ N G + ( b i , C ) , avoiding used vertices. This is possible since at most ∣ V ( F ) ∣ + 3 ( m + 1 ) ≤ 7 τ r < ( 1 − 6 τ ) r |V(F)|+3(m+1)\le7\tau r<(1-6\tau)r ∣ V ( F ) ∣ + 3 ( m + 1 ) ≤ 7 τ r < ( 1 − 6 τ ) r vertices must be avoided.
Let P = F ∪ R P=F\cup R P = F ∪ R , and write ∣ P ∣ |P| ∣ P ∣ for its number of components. By construction, every component of P P P is a ( C , B ) (C,B) ( C , B ) -path. By the construction of P P P and (10), we have ∣ P ∣ ≤ e ( F 0 ) + 1 ≤ τ r + 1 |P|\le e(F_0)+1\le\tau r+1 ∣ P ∣ ≤ e ( F 0 ) + 1 ≤ τ r + 1 and ∣ V ( P ) ∣ ≤ 7 τ r |V(P)|\le7\tau r ∣ V ( P ) ∣ ≤ 7 τ r .
e P ( C , B ) = e P ( B , A ) = e P ( A , C ) . (12) e_P(C,B)=e_P(B,A)=e_P(A,C). \tag*{(12)} e P ( C , B ) = e P ( B , A ) = e P ( A , C ) . (12)
Let G ∗ = G ∘ P G^*=G\circ P G ∗ = G ∘ P be the auxiliary tripartite digraph, whose partite classes A ′ A' A ′ , B ′ B' B ′ , C ′ C' C ′ are subsets of A A A , B B B , C C C , respectively. Let M P M_P M P denote the auxiliary matching, which has size ∣ P ∣ |P| ∣ P ∣ . Since every vertex of V ( P ) ∩ A V(P)\cap A V ( P ) ∩ A lies in V ˚ ( P ) \mathring{V}(P) V ˚ ( P ) , we have
∣ V ( P ) ∩ A ∣ = e P ( C , A ) + e P ( B , A ) = e P ( A , B ) + e P ( A , C ) . |V(P)\cap A|=e_P(C,A)+e_P(B,A)=e_P(A,B)+e_P(A,C). ∣ V ( P ) ∩ A ∣ = e P ( C , A ) + e P ( B , A ) = e P ( A , B ) + e P ( A , C ) .
Similarly, ∣ V ( P ) ∩ B ∣ = e P ( A , B ) + e P ( C , B ) |V(P)\cap B|=e_P(A,B)+e_P(C,B) ∣ V ( P ) ∩ B ∣ = e P ( A , B ) + e P ( C , B ) and ∣ V ( P ) ∩ C ∣ = e P ( C , A ) + e P ( C , B ) |V(P)\cap C|=e_P(C,A)+e_P(C,B) ∣ V ( P ) ∩ C ∣ = e P ( C , A ) + e P ( C , B ) . Combining these with (12) , we obtain ∣ V ( P ) ∩ A ∣ = ∣ V ( P ) ∩ B ∣ = ∣ V ( P ) ∩ C ∣ = : p |V(P)\cap A|=|V(P)\cap B|=|V(P)\cap C|=:p ∣ V ( P ) ∩ A ∣ = ∣ V ( P ) ∩ B ∣ = ∣ V ( P ) ∩ C ∣ =: p . Consequently, ∣ A ′ ∣ = r − p |A'|=r-p ∣ A ′ ∣ = r − p and ∣ B ′ ∣ = ∣ C ′ ∣ = : r ′ = r − p + ∣ P ∣ |B'|=|C'|=:r'=r-p+|P| ∣ B ′ ∣ = ∣ C ′ ∣ =: r ′ = r − p + ∣ P ∣ . Since p ≤ ∣ V ( P ) ∣ ≤ 7 τ r p\le|V(P)|\le7\tau r p ≤ ∣ V ( P ) ∣ ≤ 7 τ r , we have
r ′ ≥ r − p ≥ ( 1 − 7 τ ) r . (13) r'\ge r-p\ge(1-7\tau)r. \tag*{(13)} r ′ ≥ r − p ≥ ( 1 − 7 τ ) r . (13)
We now verify the hypotheses of Lemma 4.5 for G ∗ G^* G ∗ . Since every vertex of G ∗ G^* G ∗ lies outside U τ ( G , G 0 ) U_{\tau}(G,G_0) U τ ( G , G 0 ) , for v ∈ A ′ v \in A' v ∈ A ′
d G ∗ + ( v , B ′ ) ≥ d G + ( v , B ) − ( p − ∣ P ∣ ) ≥ r − 3 τ r − p + ∣ P ∣ ≥ ( 1 − 10 τ ) r ′ , d^+_{G^*}(v,B') \ge d^+_G(v,B)-(p-|P|) \ge r-3\tau r-p+|P| \ge(1-10\tau)r', d G ∗ + ( v , B ′ ) ≥ d G + ( v , B ) − ( p − ∣ P ∣ ) ≥ r − 3 τ r − p + ∣ P ∣ ≥ ( 1 − 10 τ ) r ′ ,
where the last inequality follows from (6) and (13) . All other required degree conditions follow analogously. Moreover, ( 1 − 10 τ ) r ′ ≤ ∣ A ′ ∣ ≤ r ′ (1-10\tau)r' \le|A'| \le r' ( 1 − 10 τ ) r ′ ≤ ∣ A ′ ∣ ≤ r ′ and ∣ M P ∣ = ∣ P ∣ = r ′ − ∣ A ′ ∣ |M_P|=|P|=r'-|A'| ∣ M P ∣ = ∣ P ∣ = r ′ − ∣ A ′ ∣ . Applying Lemma 4.5 to G ∗ G^* G ∗ with parameter 10 τ 10\tau 10 τ , we obtain a Hamilton cycle containing M P M_P M P . Replacing each edge of M P M_P M P with the path in P P P yields a Hamilton cycle of G G G containing R R R . Finally, for every integer 0 ≤ t ≤ m 0 \le t \le m 0 ≤ t ≤ m , replace the subpath c 0 x 1 b 1 c 1 ⋯ c t x t + 1 c_0x_1b_1c_1\cdots c_tx_{t+1} c 0 x 1 b 1 c 1 ⋯ c t x t + 1 of R R R by the edge c 0 x t + 1 c_0x_{t+1} c 0 x t + 1 . This removes exactly t t t vertices from each of A , B , C A,B,C A , B , C , yielding an ( r − t ) (r-t) ( r − t ) -balanced cycle. Therefore, we obtain a k k k -balanced cycle for every r − λ r ≤ k ≤ r r-\lambda r \le k \le r r − λ r ≤ k ≤ r .
Subcase 2.2. β ≥ σ \beta\ge\sigma β ≥ σ .
By Lemma 4.4 (ii), there exists a linear forest F F F whose components are ( C , B ) (C,B) ( C , B ) -paths, such that e ( F ) ≤ γ r e(F) \le\gamma r e ( F ) ≤ γ r , U γ ( G , G 1 ) ⊆ V ˚ ( F ) U_{\gamma}(G,G_1) \subseteq\mathring{V}(F) U γ ( G , G 1 ) ⊆ V ˚ ( F ) , and e F ( C , A ) = e F ( A , B ) e_F(C,A)=e_F(A,B) e F ( C , A ) = e F ( A , B ) , e F ( B , A ) = e F ( A , C ) e_F(B,A)=e_F(A,C) e F ( B , A ) = e F ( A , C ) . By the same argument as in Subcase 2.1, we construct a path Q = c 0 x 1 b 1 c 1 ⋯ c m x m + 1 b m + 1 Q=c_0x_1b_1c_1\cdots c_mx_{m+1}b_{m+1} Q = c 0 x 1 b 1 c 1 ⋯ c m x m + 1 b m + 1 disjoint from F F F , where c i ∈ C c_i \in C c i ∈ C , x i ∈ A ^ x_i \in\widehat{A} x i ∈ A and b i ∈ B b_i \in B b i ∈ B , such that c 0 x i ∈ E ( G ) c_0x_i \in E(G) c 0 x i ∈ E ( G ) for every i ∈ [ m + 1 ] i \in[m+1] i ∈ [ m + 1 ] . Indeed, for any c , c ′ ∈ C ∖ V ( F ) c,c' \in C \setminus V(F) c , c ′ ∈ C ∖ V ( F ) , x ∈ A ^ ∖ V ( F ) x \in\widehat{A} \setminus V(F) x ∈ A ∖ V ( F ) and b ∈ B ∖ V ( F ) b \in B \setminus V(F) b ∈ B ∖ V ( F ) , we have ∣ N G + ( c , A ^ ) ∩ N G − ( c ′ , A ^ ) ∣ ≥ ( 1 − β − 6 γ ) r |N^+_G(c,\widehat{A}) \cap N^-_G(c',\widehat{A})| \ge(1-\beta-6\gamma)r ∣ N G + ( c , A ) ∩ N G − ( c ′ , A ) ∣ ≥ ( 1 − β − 6 γ ) r , d G + ( x , B ) ≥ ( 1 − 3 γ ) r d^+_G(x,B) \ge(1-3\gamma)r d G + ( x , B ) ≥ ( 1 − 3 γ ) r and d G + ( b , C ) ≥ ( 1 − β − 3 γ ) r d^+_G(b,C) \ge(1-\beta-3\gamma)r d G + ( b , C ) ≥ ( 1 − β − 3 γ ) r . Since β ≤ 1 / 2 \beta\le1/2 β ≤ 1/2 , by (6) , ( 1 − β − 6 γ ) r ≥ ( 2 γ + 4 λ ) r ≥ ∣ V ( F ) ∣ + 3 ( m + 1 ) (1-\beta-6\gamma)r \ge(2\gamma+4\lambda)r \ge|V(F)|+3(m+1) ( 1 − β − 6 γ ) r ≥ ( 2 γ + 4 λ ) r ≥ ∣ V ( F ) ∣ + 3 ( m + 1 ) . Thus, the same greedy construction as in Subcase 2.1 applies.
Let L = F ∪ Q L=F\cup Q L = F ∪ Q . Then L L L is a linear forest whose components are ( C , B ) (C,B) ( C , B ) -paths. Moreover, U γ ( G , G 1 ) ⊆ V ˚ ( L ) U_{\gamma}(G,G_1) \subseteq\mathring{V}(L) U γ ( G , G 1 ) ⊆ V ˚ ( L ) and e L ( C , A ) = e L ( A , B ) e_L(C,A)=e_L(A,B) e L ( C , A ) = e L ( A , B ) . We also have ∣ L ∣ ≤ e ( F ) + 1 ≤ γ r + 1 |L| \le e(F)+1 \le\gamma r+1 ∣ L ∣ ≤ e ( F ) + 1 ≤ γ r + 1 and ∣ V ( L ) ∣ ≤ ( 2 γ + 4 λ ) r |V(L)| \le(2\gamma+4\lambda)r ∣ V ( L ) ∣ ≤ ( 2 γ + 4 λ ) r . Let G ∗ = G ∘ L G^*=G\circ L G ∗ = G ∘ L , and let M L M_L M L be the auxiliary matching of size ∣ L ∣ |L| ∣ L ∣ . As before, we verify the hypotheses of Lemma 4.6 for G ∗ G^* G ∗ . We have
∣ V ( L ) ∩ B ∣ = e L ( A , B ) + e L ( C , B ) = e L ( C , A ) + e L ( C , B ) = ∣ V ( L ) ∩ C ∣ . |V(L)\cap B|=e_L(A,B)+e_L(C,B)=e_L(C,A)+e_L(C,B)=|V(L)\cap C|. ∣ V ( L ) ∩ B ∣ = e L ( A , B ) + e L ( C , B ) = e L ( C , A ) + e L ( C , B ) = ∣ V ( L ) ∩ C ∣.
Let ℓ \ell ℓ denote this common value. Then ∣ B ′ ∣ = ∣ C ′ ∣ = : r ′ = r − ℓ + ∣ L ∣ |B'|=|C'|=:r'=r-\ell+|L| ∣ B ′ ∣ = ∣ C ′ ∣ =: r ′ = r − ℓ + ∣ L ∣ . Since ℓ ≤ ∣ V ( L ) ∣ ≤ ( 2 γ + 4 λ ) r \ell\le|V(L)| \le(2\gamma+4\lambda)r ℓ ≤ ∣ V ( L ) ∣ ≤ ( 2 γ + 4 λ ) r , we have
r ′ ≥ r − ℓ ≥ ( 1 − 2 γ − 4 λ ) r . (14) r' \ge r-\ell\ge(1-2\gamma-4\lambda)r. \tag*{(14)} r ′ ≥ r − ℓ ≥ ( 1 − 2 γ − 4 λ ) r . (14)
Moreover, by (6) and (14) , ∣ A ^ ′ ∣ ≤ ( 1 − β ) r ≤ ( 1 − σ ) r ≤ ( 1 − 8 η ) r ′ |\widehat{A}'| \le(1-\beta)r \le(1-\sigma)r \le(1-8\eta)r' ∣ A ′ ∣ ≤ ( 1 − β ) r ≤ ( 1 − σ ) r ≤ ( 1 − 8 η ) r ′ and ∣ A ˇ ′ ∣ ≤ β r ≤ r / 2 ≤ ( 1 − 8 η ) r ′ |\check{A}'| \le\beta r \le r/2 \le(1-8\eta)r' ∣ A ˇ ′ ∣ ≤ β r ≤ r /2 ≤ ( 1 − 8 η ) r ′ . Also, ∣ M L ∣ = ∣ L ∣ ≤ η r ′ |M_L|=|L| \le\eta r' ∣ M L ∣ = ∣ L ∣ ≤ η r ′ . Since every vertex of G ∗ G^* G ∗ lies outside U γ ( G , G 1 ) U_{\gamma}(G,G_1) U γ ( G , G 1 ) , the definition of G 1 G_1 G 1 gives
d G ∗ + ( v , B ′ ) , d G ∗ − ( v , C ′ ) ≥ r ′ − 3 γ r ( v ∈ A ^ ′ ) , d G ∗ − ( v , B ′ ) , d G ∗ + ( v , C ′ ) ≥ r ′ − 3 γ r ( v ∈ A ˇ ′ ) , d G ∗ + ( v , A ^ ′ ∪ C ′ ) , d G ∗ − ( v , A ^ ′ ∪ C ′ ) ≥ r ′ − 3 γ r − ∣ V ( L ) ∩ A ∣ ( v ∈ B ′ ) , d G ∗ + ( v , A ^ ′ ∪ B ′ ) , d G ∗ − ( v , A ^ ′ ∪ B ′ ) ≥ r ′ − 3 γ r − ∣ V ( L ) ∩ A ∣ ( v ∈ C ′ ) . \begin{aligned}
d^+_{G^*}(v,B'),\ d^-_{G^*}(v,C') &\ge r'-3\gamma r &&(v\in\widehat{A}'),\\
d^-_{G^*}(v,B'),\ d^+_{G^*}(v,C') &\ge r'-3\gamma r &&(v\in\check{A}'),\\
d^+_{G^*}(v,\widehat{A}'\cup C'),\ d^-_{G^*}(v,\widehat{A}'\cup C') &\ge r'-3\gamma r-|V(L)\cap A| &&(v\in B'),\\
d^+_{G^*}(v,\widehat{A}'\cup B'),\ d^-_{G^*}(v,\widehat{A}'\cup B') &\ge r'-3\gamma r-|V(L)\cap A| &&(v\in C').
\end{aligned} d G ∗ + ( v , B ′ ) , d G ∗ − ( v , C ′ ) d G ∗ − ( v , B ′ ) , d G ∗ + ( v , C ′ ) d G ∗ + ( v , A ′ ∪ C ′ ) , d G ∗ − ( v , A ′ ∪ C ′ ) d G ∗ + ( v , A ′ ∪ B ′ ) , d G ∗ − ( v , A ′ ∪ B ′ ) ≥ r ′ − 3 γ r ≥ r ′ − 3 γ r ≥ r ′ − 3 γ r − ∣ V ( L ) ∩ A ∣ ≥ r ′ − 3 γ r − ∣ V ( L ) ∩ A ∣ ( v ∈ A ′ ) , ( v ∈ A ˇ ′ ) , ( v ∈ B ′ ) , ( v ∈ C ′ ) .
All these bounds are at least ( 1 − η ) r ′ (1-\eta)r' ( 1 − η ) r ′ , since (6) and (14) imply that 3 γ r + ∣ V ( L ) ∩ A ∣ ≤ ( 5 γ + 4 λ ) r ≤ η r ′ 3\gamma r+|V(L)\cap A| \le(5\gamma+4\lambda)r \le\eta r' 3 γ r + ∣ V ( L ) ∩ A ∣ ≤ ( 5 γ + 4 λ ) r ≤ η r ′ . Thus, all the hypotheses of Lemma 4.6 are satisfied, and G ∗ G^* G ∗ has a Hamilton cycle containing M L M_L M L . After replacing edges of M L M_L M L by L L L gives a Hamilton cycle of G G G containing Q Q Q . As in Subcase 2.1, shortcutting Q Q Q yields a k k k -balanced cycle for every integer ( 1 − λ ) r ≤ k ≤ r (1-\lambda)r \le k \le r ( 1 − λ ) r ≤ k ≤ r .
( p , q ) (p,q) ( p , q ) -Cycle factors
Proof of Theorem 1.7 . Let n = c r n=cr n = cr and s = min { p , n − p } s=\min\{p,n-p\} s = min { p , n − p } . Suppose first that s < n / 12 s<n/12 s < n /12 . By Propositions 2.3 and 2.4 , G G G has a cycle C C C of length s s s . Let H = G − V ( C ) H=G-V(C) H = G − V ( C ) . For every v ∈ V ( H ) v \in V(H) v ∈ V ( H ) , ∣ d H ± ( v ) − ( c − 1 ) r / 2 ∣ ≤ s \lvert d_H^{\pm}(v) - (c-1)r/2\rvert\le s ∣ d H ± ( v ) − ( c − 1 ) r /2 ∣ ≤ s , so Δ 0 ( H ) − δ 0 ( H ) ≤ s \Delta^0(H)-\delta^0(H)\le s Δ 0 ( H ) − δ 0 ( H ) ≤ s . Let k 1 ≤ k 2 k_1\le k_2 k 1 ≤ k 2 be the sizes of the two largest partite classes of H H H . Since k 1 , k 2 ≤ r k_1,k_2\le r k 1 , k 2 ≤ r ,
∣ V ( H ) ∣ − k 1 − 2 k 2 + 2 2 ≥ ( c − 3 ) r − s + 2 2 ≥ s , \frac{\lvert V(H)\rvert-k_1-2k_2+2}{2}\ge\frac{(c-3)r-s+2}{2}\ge s, 2 ∣ V ( H )∣ − k 1 − 2 k 2 + 2 ≥ 2 ( c − 3 ) r − s + 2 ≥ s ,
where the last inequality follows from 3 s < n / 4 ≤ ( c − 3 ) r 3s<n/4\le(c-3)r 3 s < n /4 ≤ ( c − 3 ) r . By Proposition 2.5 , H H H has a Hamilton cycle, together with C C C forms a ( p , n − p ) (p,n-p) ( p , n − p ) -cycle factor.
Now let s ≥ n / 12 s\ge n/12 s ≥ n /12 . Choose a uniformly random p p p -set U 1 ⊆ V ( G ) U_1\subseteq V(G) U 1 ⊆ V ( G ) , and let U 2 = V ( G ) ∖ U 1 U_2=V(G)\setminus U_1 U 2 = V ( G ) ∖ U 1 . For every fixed v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , we have E [ d G ± ( v , U i ) ] = ∣ U i ∣ n d G ± ( v ) = ∣ U i ∣ ( c − 1 ) 2 c = : μ i \mathbb{E}[d_G^{\pm}(v,U_i)]=\frac{\lvert U_i\rvert}{n}d_G^{\pm}(v)=\frac{\lvert U_i\rvert(c-1)}{2c}=:\mu_i E [ d G ± ( v , U i )] = n ∣ U i ∣ d G ± ( v ) = 2 c ∣ U i ∣ ( c − 1 ) =: μ i . By Lemma 2.13 , for every fixed v ∈ V ( G ) v\in V(G) v ∈ V ( G ) and i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] ,
P ( ∣ d G ± ( v , U i ) − μ i ∣ > ∣ U i ∣ 28 ) ≤ 2 exp ( − ∣ U i ∣ 400 ) . (15) \mathbb{P}\left(\lvert d_G^{\pm}(v,U_i)-\mu_i\rvert>\frac{\lvert U_i\rvert}{28}\right)\le2\exp\left(-\frac{\lvert U_i\rvert}{400}\right). \tag*{(15)} P ( ∣ d G ± ( v , U i ) − μ i ∣ > 28 ∣ U i ∣ ) ≤ 2 exp ( − 400 ∣ U i ∣ ) . (15)
For each partite class V j V_j V j , E ( ∣ V j ∩ U i ∣ ) = ∣ U i ∣ / c \mathbb{E}(\lvert V_j\cap U_i\rvert)=\lvert U_i\rvert/c E (∣ V j ∩ U i ∣) = ∣ U i ∣ / c , so
P ( ∣ ∣ V j ∩ U i ∣ − ∣ U i ∣ c ∣ > ∣ U i ∣ 28 ) ≤ 2 exp ( − ∣ U i ∣ 400 ) . (16) \mathbb{P}\left(\left\lvert\lvert V_j\cap U_i\rvert-\frac{\lvert U_i\rvert}{c}\right\rvert>\frac{\lvert U_i\rvert}{28}\right)\le2\exp\left(-\frac{\lvert U_i\rvert}{400}\right). \tag*{(16)} P ( ∣ V j ∩ U i ∣ − c ∣ U i ∣ > 28 ∣ U i ∣ ) ≤ 2 exp ( − 400 ∣ U i ∣ ) . (16)
By the union bound and (14) and (15) there exists a partition { U 1 , U 2 } \{U_1,U_2\} { U 1 , U 2 } such that, for each v ∈ U i v\in U_i v ∈ U i , ∣ d ± ( v , U i ) − μ i ∣ ≤ ∣ U i ∣ / 28 \lvert d^{\pm}(v,U_i)-\mu_i\rvert\le\lvert U_i\rvert/28 ∣ d ± ( v , U i ) − μ i ∣ ≤ ∣ U i ∣ /28 , and ∣ V j ∩ U i ∣ ≤ ∣ U i ∣ / c + ∣ U i ∣ / 28 ≤ 2 ∣ U i ∣ / 7 \lvert V_j\cap U_i\rvert\le\lvert U_i\rvert/c+\lvert U_i\rvert/28\le2\lvert U_i\rvert/7 ∣ V j ∩ U i ∣ ≤ ∣ U i ∣ / c + ∣ U i ∣ /28 ≤ 2 ∣ U i ∣ /7 for i ∈ [ 2 ] i\in[2] i ∈ [ 2 ] and j ∈ [ c ] j\in[c] j ∈ [ c ] , because ( 8 n + 4 c ) exp ( − s / 400 ) < 1 (8n+4c)\exp(-s/400)<1 ( 8 n + 4 c ) exp ( − s /400 ) < 1 and c ≥ 4 c\ge4 c ≥ 4 . Let m i , 1 ≤ m i , 2 m_{i,1}\le m_{i,2} m i , 1 ≤ m i , 2 be the sizes of the two largest partite classes of G [ U i ] G[U_i] G [ U i ] .
Δ 0 ( G [ U i ] ) − δ 0 ( G [ U i ] ) ≤ ∣ U i ∣ 14 ≤ ∣ U i ∣ − m i , 1 − 2 m i , 2 + 2 2 . \Delta^0(G[U_i])-\delta^0(G[U_i])\le\frac{\lvert U_i\rvert}{14}\le\frac{\lvert U_i\rvert-m_{i,1}-2m_{i,2}+2}{2}. Δ 0 ( G [ U i ]) − δ 0 ( G [ U i ]) ≤ 14 ∣ U i ∣ ≤ 2 ∣ U i ∣ − m i , 1 − 2 m i , 2 + 2 .
By Proposition 2.5 , each of G [ U 1 ] G[U_1] G [ U 1 ] and G [ U 2 ] G[U_2] G [ U 2 ] has a Hamilton cycle. These two vertex-disjoint Hamilton cycles form the required ( p , n − p ) (p,n-p) ( p , n − p ) -cycle-factor, completing the proof.
Declaration of AI. The authors used GPT-5.6 Sol as a research assistance tool during the preparation of this manuscript. In particular, while investigating the case of regular tripartite tournaments, the AI helped identify an important reference. The arguments presented in § 3.1 and § 3.2 make substantial use of techniques and lemmas developed in that reference, which is acknowledged and cited in the manuscript. The authors also used AI to assist with language editing, typesetting, and checking the correctness of mathematical arguments. The authors have carefully reviewed the manuscript and take full responsibility for its mathematical correctness, accuracy, and content.
Acknowledgments. We thank Yangyang Cheng for bringing these problems to our attention and sharing his insights with us.