betaFeedback

WorksMathematics

Cycles in Regular Multipartite Tournaments

Abstract

We study balanced cycles in regular multipartite tournaments. A cycle in a cc-partite tournament is kk-balanced if it contains exactly kk vertices from each partite class. We prove that there exists an absolute integer r0r_0 such that every regular cc-partite tournament with each partite class size of r≥r0r\ge r_0 contains a kk-balanced cycle for every 1≤k≤r1\le k\le r when c=3c=3 or c≥5c\ge5, and for every 2≤k≤r2\le k\le r when c=4c=4. In particular, our result confirms three conjectures of Volkmann and Winzen for large regular multipartite tournaments. We also confirm Yeo's conjecture on the existence of (p,q)(p,q)-cycle factors for large regular cc-partite tournaments GG with c≥4c\ge4, where a (p,q)(p,q)-cycle factor is a pair of vertex-disjoint cycles of lengths pp and qq spanning GG.

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 nn vertices is vertex-pancyclic, meaning that every vertex lies on a cycle of each length from 3 to nn.

A cc-partite tournament is an orientation of a complete cc-partite graph. For a vertex vv, let d+(v)d^{+}(v) and d−(v)d^{-}(v) denote its outdegree and indegree, respectively. A cc-partite tournament is dd-regular if d+(v)=d−(v)=dd^{+}(v) = d^{-}(v) = d for every vertex vv. In this case, all partite classes have the same size rr, and d=(c−1)r/2d = (c - 1)r/2. A natural question is whether similar pancyclicity results hold for regular cc-partite tournaments. Yeo [23] proved that every regular cc-partite tournament is vertex-pancyclic when c≥5c \ge5. However, this fails for c=3c = 3. Indeed, consider the regular 3-partite tournament with all edges directed from ViV_i to Vi+1V_{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, 3r3r and 3r−33r - 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 rr vertices in each class contains a cycle of length 3k3k for every 1≤k≤r1 \le k \le r.

Stella and Volkmann [13] proved the case k=3k = 3 later. A path or cycle is kk-balanced if it contains exactly kk vertices from each partite class, and simply balanced if k=1k = 1. Volkmann and Winzen [19] proved that every regular cc-partite tournament with c≥5c \ge5 contains an (r−1)(r - 1)-balanced cycle. More generally, they showed that, for every fixed positive integer ss, such a tournament contains an (r−s)(r - s)-balanced cycle whenever rr is sufficiently large. They further conjectured the following.

Conjecture 1.2 (Volkmann and Winzen [19]). Every regular cc-partite tournament with c≥5c \ge5 and common partite size rr contains a kk-balanced cycle for every 1≤k≤r1 \le k \le r.

The case k=1k = 1 was later settled in [20]. The condition c≥5c \ge5 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 cc-partite tournament with c≥2c \ge2 and common partite size rr contains a kk-balanced path for every 1≤k≤r1 \le k \le r.

The conjecture is known to hold for c=2c = 2, and the cases k∈{1,2,r−1,r}k \in\{1, 2, r - 1, r\} have been established for all c≥2c \ge2 in [18]. Our first result confirms Conjectures 1.1 to 1.3 for all r≥r0r \ge r_0, where r0r_0 is an absolute constant.

Theorem 1.4. There exists a positive integer r0r_0 such that for every c≥3c \ge3 and r≥r0r \ge r_0, every regular cc-partite tournament with common partite size rr contains a kk-balanced cycle for every $1 \le k \le r$ if c=3c = 3 or c≥5c \ge5, and for every 2≤k≤r2 \le k \le r if $c = 4.

We also study (p,q)(p, q)-cycle-factors in regular cc-partite tournaments. A (p,q)(p, q)-cycle-factor consists of two vertex-disjoint cycles of lengths pp and qq that together cover all vertices. Yeo [23] proposed the following conjecture.

Conjecture 1.5 (Yeo [23]). Every regular cc-partite tournament GG with c≥5c \ge5 contains a (p,∣V(G)∣−p)(p, \lvert V(G) \rvert- p)-cycle-factor for every 3≤p≤∣V(G)∣−33 \le p \le\lvert V(G) \rvert- 3.

Bessy and Thiebaut [1] proposed a weaker conjecture under a stronger regularity condition.

Conjecture 1.6 (Bessy and Thiebaut [1]). Every cc-partite tournament GG with c≥5c \ge5, in which the bipartite tournament between any two partite classes is tt-regular, contains a (p,∣V(G)∣−p)(p, \lvert V(G) \rvert- p)-cycle-factor for every even integer 4≤p≤∣V(G)∣−44 \le p \le\lvert V(G) \rvert- 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=4c = 4.

Theorem 1.7. There exists a positive integer r0r_0 such that for every c≥4c \ge4 and r≥r0r \ge r_0, every regular cc-partite tournament GG with common partite size rr contains a (p,cr−p)(p, cr - p)-cycle-factor for every 3≤p≤cr−33 \le p \le cr - 3.

Organization. In § 1, we collect the preliminary results. In § 2, we prove Theorem 1.4 for c≥4c \ge4. 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 GG be a digraph. For v∈V(G)v \in V(G), let NG+(v)={u:vu∈E(G)}N_G^{+}(v) = \{u : vu \in E(G)\} and NG−(v)={u:uv∈E(G)}N_G^{-}(v) = \{u : uv \in E(G)\} be its out- and in-neighborhoods, respectively, and dG±(v)=∣NG±(v)∣d_G^{\pm}(v) = |N_G^{\pm}(v)|. For B⊆V(G)B \subseteq V(G), set dG+(v,B)=∣NG+(v)∩B∣d_G^{+}(v, B) = |N_G^{+}(v) \cap B| and dG(v,B)=dG+(v,B)+dG−(v,B)d_G(v, B) = d_G^{+}(v, B) + d_G^{-}(v, B). The total degree of vv is dG(v)=dG+(v)+dG−(v)d_G(v) = d_G^{+}(v) + d_G^{-}(v), and the minimum total degree of GG is δ(G)\delta(G). The minimum and maximum semidegrees are δ0(G)=min⁡v∈V(G)min⁡{dG+(v),dG−(v)}\delta^{0}(G) = \min_{v \in V(G)} \min\{d_G^{+}(v), d_G^{-}(v)\} and Δ0(G)=max⁡v∈V(G)max⁡{dG+(v),dG−(v)}\Delta^{0}(G) = \max_{v \in V(G)} \max\{d_G^{+}(v), d_G^{-}(v)\}. A vertex vv of a tournament TT is a source if dT−(v)=0d_T^{-}(v) = 0 and a sink if dT+(v)=0d_T^{+}(v) = 0.

For x,y∈V(G)x, y \in V(G), write x→yx \to y (or xyxy) if xy∈E(G)xy \in E(G), and x→y→zx \to y \to z if xy,yz∈E(G)xy, yz \in E(G). For disjoint sets A,B⊆V(G)A, B \subseteq V(G), write A→BA \to B if a→ba \to b for all a∈Aa \in A and b∈Bb \in B. For any A,B⊆V(G)A, B \subseteq V(G), let EG(A,B)={xy∈E(G):x∈A,y∈B}E_G(A, B) = \{xy \in E(G) : x \in A, y \in B\}, and eG(A,B)=∣EG(A,B)∣=∑v∈AdG+(v,B)e_G(A, B) = |E_G(A, B)| = \sum_{v \in A} d_G^{+}(v, B). We omit the subscript GG when clear. An (A,B)(A, B)-path (resp. (A,B)(A, B)-edge) is a path (resp. edge) from AA to BB. In particular, an (a,b)(a, b)-path is a path from aa to bb.

A linear forest P=P1∪⋯∪PtP = P_1 \cup\cdots\cup P_t consists of nontrivial vertex-disjoint paths, where each PiP_i is an (ai,bi)(a_i, b_i)-path. Let V˚(P)\mathring{V}(P) be the set of its internal vertices. Then ∣V(P)∣≤2e(P)|V(P)| \le2e(P). We write G∘PG \circ P for the digraph obtained by deleting V˚(P)\mathring{V}(P), adding the edges aibia_i b_i for all i∈[t]i \in[t], and retaining all other edges between the remaining vertices. These added edges form the auxiliary matching MP={aibi:i∈[t]}M_P = \{a_i b_i : i \in[t]\}.

For disjoint sets A,BA, B, let M[A,B]M[A, B] denote a matching directed from AA to BB with ∣M[A,B]∣=∣A∣=∣B∣|M[A, B]| = |A| = |B|.

A hypergraph H\mathcal{H} consists of a vertex set V(H)V(\mathcal{H}) and an edge set E(H)⊆2V(H)E(\mathcal{H}) \subseteq2^{V(\mathcal{H})}. It is kk-uniform if every edge has size kk, and cc-partite if its vertices can be partitioned into cc classes, each meeting every edge in at most one vertex. The complete cc-partite kk-uniform hypergraph Kℓ1,…,ℓc(k)K^{(k)}_{\ell_1,\ldots,\ell_c} has vertex classes of sizes ℓ1,…,ℓc\ell_1,\ldots,\ell_c and contains all kk-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] such that the result holds for all $0 < a, b, c \le 1$ with b≤f(c)b \le f(c) and a≤g(b)a \le 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 cc-partite tournament with c≥5c \ge5 is vertex-pancyclic.

Proposition 2.4 (Yeo [24]). Every sufficiently large regular four-partite tournament is vertex-pancyclic.

References

  1. [1]S. Bessy and J. Thiebaut, Complementary cycles of any length in regular bipartite tournaments, \textit{J. Graph Theory} 103 (2023), 186–211.arxiv.org/abs/2102.04514
  2. [2]J. A. Bondy, Disconnected orientations and a conjecture of Las Vergnas, \textit{J. Lond. Math. Soc.} 14 (1976), 277–282.DOI
  3. [3]P. Camion, Chemins et circuits hamiltoniens des graphes complets, \textit{C. R. Acad. Sci. Paris} 249 (1959), 2151–2152.
  4. [4]F. Di Braccio, J. Lada, V. Patel, Y. Pehova, and J. Skokan, Hamilton decompositions of regular tripartite tournaments, arXiv:2507.12460 (2025).arxiv.org/abs/2507.12460
  5. [5]P. Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190.DOI
  6. [6]A. Girão, B. Granet, D. Kühn, A. Lo, and D. Osthus, Path decompositions of tournaments, Proc. Lond. Math. Soc. 126 (2023), 429–517.
  7. [7]W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30.
  8. [8]J. Komlós, G. N. Sárközy, and E. Szemerédi, Blow-up lemma, Combinatorica 17 (1997), 109–123.
  9. [9]D. Kühn, D. Osthus, and A. Taraz, Large planar subgraphs in dense graphs, J. Combin. Theory Ser. B 95 (2005), 263–282.DOI
  10. [10]A. Lo and V. Patel, Hamilton cycles in sparse robustly expanding digraphs, Electron. J. Combin. 25 (2018), Paper 3.44.arxiv.org/abs/1507.04472
  11. [11]J. W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9 (1966), 297–301.DOI
  12. [12]L. Rédei, Ein kombinatorischer Satz, Acta Litt. Sci. Szeged 7 (1934), 39–43.
  13. [13]I. Stella and L. Volkmann, Each regular 3-partite tournament has a 9-cycle, An. Univ. București Mat. 56 (2007), 91–120.
  14. [14]L. Volkmann, Strong subtournaments of multipartite tournaments, Australas. J. Combin. 20 (1999), 189–196.
  15. [15]L. Volkmann, Complementary cycles in regular multipartite tournaments, where one cycle has length four, Kyungpook Math. J. 44 (2004), 219–247.
  16. [16]L. Volkmann, All regular multipartite tournaments that are cycle complementary, Discrete Math. 281 (2004), 255–266.DOI
  17. [17]L. Volkmann, On cycles in regular 3-partite tournaments, Discrete Math. 306 (2006), 1198–1206.DOI
  18. [18]L. Volkmann and S. Winzen, Paths with a given number of vertices from each partite set in regular multipartite tournaments, Discrete Math. 306 (2006), 2724–2732.DOI
  19. [19]L. Volkmann and S. Winzen, Cycles with a given number of vertices from each partite set in regular multipartite tournaments, Czechoslovak Math. J. 56 (2006), 827–843.DOI
  20. [20]L. Volkmann and S. Winzen, Almost regular c-partite tournaments contain a strong subtournament of order c when c ≥ 5, Discrete Math. 308 (2008), 1710–1721.DOI
  21. [21]A. Yeo, One-diregular subgraphs in semicomplete multipartite digraphs, J. Graph Theory 24 (1997), 175–185.doi.org/10.1002/(sici)1097-0118(199702)24:2<175::aid-jgt5>3.0.co;2-n
  22. [22]A. Yeo, How close to regular must a semicomplete multipartite digraph be to secure hamiltonicity?, Graphs Combin. 15 (1999), 481–493.DOI
  23. [23]A. Yeo, Diregular c-partite tournaments are vertex-pancyclic when c ≥ 5, J. Graph Theory 32 (1999), 137–152.doi.org/10.1002/(sici)1097-0118(199910)32:2<137::aid-jgt4>3.0.co;2-i
  24. [24]A. Yeo, Paths and cycles containing given arcs, in close to regular multipartite tournaments, J. Combin. Theory Ser. B 97 (2007), 949–963.DOI

Paper details

vlnc:W_f6am6dw2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents