pith. sign in

arxiv: 2604.13700 · v2 · submitted 2026-04-15 · 🧮 math.CO

Openly disjoint cycles and directed tree-width of regular digraphs

Raphael Steiner This is my paper

Pith reviewed 2026-05-10 13:13 UTC · model grok-4.3

classification 🧮 math.CO
keywords regular digraphsopenly disjoint cyclesdirected tree-widthMader conjecturedigraph subdivisionsCaccetta-Haggkvist conjecture
0
0 comments X

The pith

Every r-regular digraph contains at least ceil(3r/22) openly disjoint cycles through some vertex.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies how many directed cycles can share a single vertex while remaining vertex-disjoint away from that vertex in regular digraphs. It establishes a linear lower bound on this number in terms of the degree r, proving that the minimum guaranteed value grows proportionally to r rather than staying bounded. This confirms a conjecture that such numbers must increase without limit as degree rises. The same work shows that the directed tree-width of any r-regular digraph is linear in r and derives degree conditions that force the presence of large subdivided cylindrical walls.

Core claim

We prove that for every natural number r, the minimum over all r-regular digraphs D of the largest number k such that D has k openly disjoint cycles through a common vertex is at least ceil(3r/22). We also prove an upper bound of 7 ceil(r/8) on this minimum. In addition, every r-regular digraph has directed tree-width Omega(r), which is tight up to the constant factor and yields a function f such that any regular digraph of degree at least f(k) contains a subdivision of the cylindrical wall of order k.

What carries the argument

The function c_r, the smallest possible value of the maximum number of openly disjoint cycles through one vertex across all r-regular digraphs, together with the directed tree-width measure that quantifies how far a digraph is from being tree-like.

If this is right

  • Mader's conjecture that the minimum number of openly disjoint cycles through a vertex grows unboundedly with degree is settled with an explicit linear rate.
  • The best known upper bound on the minimum number of such cycles is improved to roughly 7r/8.
  • Every r-regular digraph contains a subdivision of the cylindrical wall of order k once r exceeds some threshold depending only on k.
  • The linear directed tree-width lower bound fails if the regularity assumption is relaxed to mere minimum in-degree and out-degree r.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Regularity imposes a much stricter global cycle structure than minimum-degree conditions alone in the directed setting.
  • The linear tree-width result suggests that attempts to force large digraph subdivisions will need to exploit regularity rather than average degree.
  • Improving the constant 3/22 would require new extremal constructions that still respect regularity while reducing the cycle packing number.

Load-bearing premise

The combinatorial constructions and inductive arguments used to obtain the concrete factor 3/22 correctly cover every possible r-regular digraph without missing counterexamples that would force a smaller ratio.

What would settle it

An explicit construction of an r-regular digraph for arbitrarily large r in which no vertex lies on more than 3r/22 minus one openly disjoint cycles would refute the lower bound.

Figures

Figures reproduced from arXiv: 2604.13700 by Raphael Steiner.

Figure 1
Figure 1. Figure 1: Illustration of the cylindrical wall of order 4. The indicated half-arcs loop back from the top-row of the wall to the bottom-row (without crossings). Kreutzer [14], one of the premier results of structural digraph theory, which extends Robertson and Seymour’s famous grid minor theorem [26] to directed graphs. To state the result, we first define the so-called cylindrical walls. Definition 1 (Cylindrical w… view at source ↗
read the original abstract

Given a digraph $D$, let $c(D)$ denote the largest integer $k$ such that there are $k$ openly disjoint cycles through a vertex, i.e., a collection of directed cycles $C_1,\ldots,C_k$ through a common vertex $v$ such that $C_1-v,\ldots,C_k-v$ are pairwise vertex-disjoint. The famous Caccetta-H\"aggkvist conjecture and its regular variant due to Behzad, Chartrand and Wall from 1970, have motivated the study of degree conditions forcing $c(D)$ to be large. In 1985 Thomassen constructed digraphs of arbitrarily high minimum out- and in-degree such that $c(D)\le 2$. In 2005, Seymour asked whether in contrast every $r$-regular digraph satisfies $c(D)=r$, which would have implied the Behzad-Chartrand-Wall conjecture. In 2008, Mader answered this negatively for every $r\ge 8$, but conjectured that nevertheless the minimum value $c_r$ of $c(D)$ over all $r$-regular digraphs grows with $r$, i.e. $\lim_{r\rightarrow\infty}c_r=\infty$. As the first main result of our paper, we prove Mader's conjecture in a strong form by showing $c_r\ge \lceil\frac{3}{22} r\rceil$ for every $r\in \mathbb{N}$. We also show $c_r\le 7\left\lceil \frac{r}{8}\right\rceil$, improving the previous best upper bound $c_r\le r-\Theta(\sqrt{r})$ due to Mader. In our second main result we show that every $r$-regular digraph has directed tree-width $\Omega(r)$. This is tight up to the implied constant and cannot be extended to digraphs of minimum out- and in-degree at least $r$. As a corollary we obtain the existence of a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every regular digraph with degree at least $f(k)$ contains a subdivision of the cylindrical wall of order $k$, and hence of a large class of planar digraphs. This makes progress on the notoriously difficult problem of finding degree conditions guaranteeing subdivisions of digraphs, related to a well-known conjecture of Mader from 1985.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves Mader's conjecture in quantitative form by establishing that every r-regular digraph D satisfies c(D) ≥ ⌈(3/22)r⌉, where c(D) is the largest number of openly disjoint directed cycles through a common vertex; it also supplies the matching upper bound c_r ≤ 7⌈r/8⌉. A second main result shows that the directed tree-width of any r-regular digraph is Ω(r), which is asymptotically tight and fails to extend to digraphs of minimum in- and out-degree r. As a corollary, sufficiently high-degree regular digraphs contain subdivisions of arbitrarily large cylindrical walls.

Significance. The linear lower bound on c_r is the first of its kind and directly resolves the qualitative conjecture of Mader; the tree-width result supplies the first linear lower bound for regular digraphs and yields new progress on Mader's 1985 subdivision conjecture. The proofs are explicit, track the regularity hypothesis through all reductions, and include matching constructions that establish tightness up to the constant factor.

minor comments (3)
  1. [§2] §2, Definition 2.3: the notation for openly disjoint cycles is introduced without an accompanying diagram; a small illustrative figure would improve readability for readers unfamiliar with the concept.
  2. [Introduction] Theorem 1.1 and Theorem 1.3: the statements of the two main theorems use slightly different conventions for the ceiling function; harmonizing the notation (e.g., always writing ⌈3r/22⌉) would aid cross-reference.
  3. [§4.2] §4.2, the inductive step for the lower bound on c_r: the case distinction for r ≡ 2 mod 4 is handled by a separate lemma; a one-sentence pointer back to the main induction hypothesis would make the flow clearer.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our results, the recognition of their significance in resolving Mader's conjecture quantitatively and providing the first linear lower bound on directed tree-width for regular digraphs, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript establishes lower and upper bounds on c_r and an Omega(r) bound on directed tree-width via explicit inductive and extremal combinatorial arguments that track the regularity hypothesis through each reduction step with case distinctions. These derivations are self-contained first-principles proofs of Mader's conjecture and related results; they do not reduce any claimed prediction or theorem to a fitted parameter, self-definition, or load-bearing self-citation whose validity depends on the present paper. The abstract and skeptic summary confirm the proofs are direct and do not invoke uniqueness theorems or ansatzes imported from prior author work in a circular manner. This is the expected outcome for a pure existence/proof paper in extremal graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard axioms of directed graph theory such as the definition of cycles and regularity; no free parameters, invented entities, or ad-hoc assumptions are mentioned in the abstract.

axioms (1)
  • standard math Standard definitions and basic properties of directed graphs, cycles, and regularity
    Invoked implicitly throughout the statements of c(D) and directed tree-width.

pith-pipeline@v0.9.0 · 5754 in / 1381 out tokens · 47601 ms · 2026-05-10T13:13:36.401238+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Aboulker, N

    P. Aboulker, N. Cohen, F. Havet, W. Lochet, P. F. S. Moura, and S. Thomass´ e. Subdivi- sions in digraphs of large out-degree or large dichromatic number.Electron. J. Combin., 26(3):Paper No. 3.19, 18, 2019

    work page 2019

  2. [2]

    Behzad, G

    M. Behzad, G. Chartrand, and C. E. Wall. On minimal regular digraphs with given girth. Fund. Math., 69:227–231, 1970

    work page 1970

  3. [3]

    Bensmail, V

    J. Bensmail, V. Campos, A. K. Maia, N. Nisse, and A. Silva. Deciding the Erd˝ os-P´ osa property in 3-connected digraphs. InGraph-theoretic concepts in computer science, volume 14093 ofLecture Notes in Comput. Sci., pages 59–71. Springer, Cham, [2023]©2023

    work page 2023

  4. [4]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason. Proof of a conjecture of Mader, Erd˝ os and Hajnal on topological complete subgraphs.European J. Combin., 19(8):883–887, 1998

    work page 1998

  5. [5]

    Caccetta and R

    L. Caccetta and R. H¨ aggkvist. On minimal digraphs with given girth. InProceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), volume XXI ofCongress. Numer., pages 181–187. Utilitas Math., Winnipeg, MB, 1978

    work page 1978

  6. [6]

    Chv´ atal and E

    V. Chv´ atal and E. Szemer´ edi. Short cycles in directed graphs.J. Combin. Theory Ser. B, 35(3):323–327, 1983

    work page 1983

  7. [7]

    A. C. Giannopoulou, K.-i. Kawarabayashi, S. Kreutzer, and O.-j. Kwon. The directed flat wall theorem. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 239–258. SIAM, Philadelphia, PA, 2020

    work page 2020

  8. [8]

    Gir˜ ao and S

    A. Gir˜ ao and S. Letzter. Immersion of complete digraphs in Eulerian digraphs.Israel J. Math., 260(1):401–425, 2024

    work page 2024

  9. [9]

    Gir˜ ao, K

    A. Gir˜ ao, K. Popielarz, and R. Snyder. Subdivisions of digraphs in tournaments.J. Combin. Theory Ser. B, 146:266–285, 2021

    work page 2021

  10. [10]

    Gishboliner, R

    L. Gishboliner, R. Steiner, and T. Szab´ o. Oriented cycles in digraphs of large outdegree. Combinatorica, 42:1145–1187, 2022

    work page 2022

  11. [11]

    Hladk´ y, D

    J. Hladk´ y, D. Kr´ al’, and S. Norin. Counting flags in triangle-free digraphs.Combinatorica, 37(1):49–76, 2017

    work page 2017

  12. [12]

    C. T. Ho` ang and B. Reed. A note on short cycles in digraphs.Discrete Math., 66(1-2):103– 107, 1987

    work page 1987

  13. [13]

    Johnson, N

    T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Directed tree-width.J. Combin. Theory Ser. B, 82(1):138–154, 2001

    work page 2001

  14. [14]

    Kawarabayashi and S

    K.-i. Kawarabayashi and S. Kreutzer. The directed grid theorem. InSTOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, pages 655–664. ACM, New York, 2015. 15

    work page 2015

  15. [15]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi. Topological cliques in graphs.Combin. Probab. Comput., 3(2):247–256, 1994

    work page 1994

  16. [16]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi. Topological cliques in graphs. II.Combin. Probab. Comput., 5(1):79–90, 1996

    work page 1996

  17. [17]

    K¨ uhn, D

    D. K¨ uhn, D. Osthus, and A. Young. A note on complete subdivisions in digraphs of large outdegree.J. Graph Theory, 57(1):1–6, 2008

    work page 2008

  18. [18]

    W. Lochet. Immersion of transitive tournaments in digraphs with large minimum outdegree. J. Combin. Theory Ser. B, 134:350–353, 2019

    work page 2019

  19. [19]

    W. Mader. Existenzn-fach zusammenh¨ angender Teilgraphen in Graphen gen¨ ugend grosser Kantendichte.Abh. Math. Sem. Univ. Hamburg, 37:86–97, 1972

    work page 1972

  20. [20]

    W. Mader. Degree and local connectivity in digraphs.Combinatorica, 5(2):161–165, 1985

    work page 1985

  21. [21]

    W. Mader. Existence of vertices of local connectivitykin digraphs of large outdegree. Combinatorica, 15(4):533–539, 1995

    work page 1995

  22. [22]

    W. Mader. On topological tournaments of order 4 in digraphs of outdegree 3.J. Graph Theory, 21(4):371–376, 1996

    work page 1996

  23. [23]

    W. Mader. Existence of openly disjoint circuits through a vertex.J. Graph Theory, 63(2):93– 105, 2010

    work page 2010

  24. [24]

    W. Mader. Openly disjoint circuits through a vertex in regular digraphs.Discrete Math., 310(20):2671–2674, 2010

    work page 2010

  25. [25]

    B. Reed. Introducing directed tree width. In6th Twente Workshop on Graphs and Combi- natorial Optimization (Enschede, 1999), volume 3 ofElectron. Notes Discrete Math., page 8. Elsevier Sci. B. V., Amsterdam, 1999

    work page 1999

  26. [26]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph.J. Combin. Theory Ser. B, 41(1):92–114, 1986

    work page 1986

  27. [27]

    R. M. Steiner. Disjoint cycles with length constraints in digraphs of large connectivity or large minimum degree.SIAM J. Discrete Math., 36(2):1343–1362, 2022

    work page 2022

  28. [28]

    B. D. Sullivan. A summary of problems and results related to the caccetta-haggkvist con- jecture.arXiv preprint math/0605646, 2006

    work page arXiv 2006

  29. [29]

    Thomassen

    C. Thomassen. The 2-linkage problem for acyclic digraphs.Discrete Math., 55(1):73–87, 1985

    work page 1985

  30. [30]

    Thomassen

    C. Thomassen. Even cycles in directed graphs.European J. Combin., 6(1):85–89, 1985. 16

    work page 1985