{"id":"686ed996-f1f9-4b3f-b41a-3966e5695049","arxiv_id":"2507.11814","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every digraph of sufficiently large cycle rank contains a directed ladder, a directed cycle chain, or a directed tree chain of order k as a butterfly minor.","lead":"A new theorem shows that every digraph with sufficiently large cycle rank must contain one of three explicitly described structures as a butterfly minor. This gives the first finite list of unavoidable obstructions for a classic digraph depth parameter, and connects cycle rank to a directed version of weak coloring numbers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof gap: Lemma 7.17's minimality argument assumes the chain decomposition from Lemma 7.6 outcome (2) is clean, but that outcome does not guarantee cleanliness.","rationale":"The reader identified the directed grid theorem as the weakest assumption. That is an external dependency, but it is a published theorem and the paper's use of it appears standard. In contrast, the gap I found is internal and occurs in the proof of Lemma 7.17, which is essential for the proof of Theorem 1.1. The proof of Lemma 7.17 selects a butterfly minor with a clean chain decomposition minimizing i, applies Lemma 7.6, and in the case of outcome (2) uses the resulting T'' to contradict the minimality of i. But Lemma 7.6 outcome (2) does not state that T'' is clean, and the construction via Lemma 7.4 gives no preservation guarantee. Unless this can be repaired, the existence of a spotless chain decomposition of large height is not established, and hence Lemma 7.14 cannot be applied. This is a concrete, testable gap rather than a vague worry. I recommend a conditional acceptance pending verification or repair of this step. I found the rest of the structure coherent: the reductions in Theorem 7.2, the weight-descent arguments in Lemmas 7.16 and 7.17, and the extraction lemma 7.14 are all plausible, and aside from the identified gap I have no further objection.","tokens_in":51898,"tokens_out":36198,"duration_ms":393945,"concrete_test":"Check whether the chain decomposition T' produced in Lemma 7.6 outcome (2) via Lemma 7.4 is clean whenever the input T is clean. Concretely, instantiate the smallest bad-triple configuration from Lemma 7.6 (e.g., Case 2.1 with k1 = 2), apply the prescribed modification, and verify the clean property at every node of the resulting decomposition. If cleanliness fails, the minimality argument in Lemma 7.17 collapses and the proof needs an additional argument to either force outcome (1) or restore cleanliness.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Lemma 7.17 (the step that produces a spotless chain decomposition) chooses a butterfly minor F' with a clean chain decomposition T' minimizing i, then applies Lemma 7.6. If Lemma 7.6 returns outcome (2), it guarantees only that T'' has full height at least ik and that its weight vector is lexicographically larger; it does not assert that T'' is clean. Nevertheless, the proof of Lemma 7.17 uses T'' to construct a contradiction by claiming a smaller i1 < i with a clean chain decomposition. This inference requires T'' to be clean, which is not established. The missing cleanliness is not a cosmetic issue: Lemma 7.6 constructs outcome (2) via Lemma 7.4, and Lemma 7.4 neither states nor proves that the 'clean' property is preserved under its tree modification. Since Lemma 7.17 is the only route from a clean decomposition to a spotless decomposition of large full height, and the final extraction of TC_k (Lemma 7.14) needs a spotless decomposition, this gap is directly load-bearing for Theorem 1.1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an unavoidable-minors theorem for cycle rank in digraphs: there is a function f such that every digraph with cycle rank at least f(k) contains a directed ladder L_k, a directed cycle chain CC_k, or a directed tree chain TC_k as a butterfly minor. From this it derives a characterization of butterfly-minor-closed classes of bounded cycle rank, and it proves a new relation equating cycle rank with the weak (∞,→)-coloring number minus one. The proof combines the directed grid theorem with an Erdős–Pósa argument, introduces chain decompositions and auxiliary notions of clean and spotless decompositions, and then extracts one of the three obstructions. The paper also proves pairwise independence of the three obstruction families.","tokens_in":52079,"tokens_out":19823,"duration_ms":236761,"significance":"If the main theorem is correct, it resolves a natural open problem in the area of digraph width parameters. The obstruction families are simple and explicit, and the resulting characterization of butterfly-minor-closed classes of bounded cycle rank is a strong structural statement. The proof is long but mostly self-contained, and it includes a direct proof of monotonicity of cycle rank under butterfly minors and a short, clean proof of the weak-coloring-number characterization in Section 9. The main result is conditional on the directed grid theorem, which is a standard external dependency rather than a circularity. However, the iterative refinement argument in Section 7 contains two load-bearing gaps, described below, so the significance is conditional on those gaps being repaired.","major_comments":[{"comment":"The proof of Lemma 7.17 applies Lemma 7.6 and then refers to the resulting decomposition T'' as a clean chain decomposition satisfying one of the three outcomes. This is not what Lemma 7.6 states: only outcomes (1) and (3) assert cleanliness, while outcome (2) is stated only for a chain decomposition. The proof of outcome (2) goes through Lemma 7.4, whose statement and proof do not establish that the clean property is preserved under the tree modification. Since the minimality condition in Lemma 7.17 is over clean chain decompositions, the contradiction producing a smaller i1 requires T'' to be clean, and this is not supplied. This gap is load-bearing for the extraction of a spotless decomposition and hence for the proof of Theorem 1.1.","section":"§7, Lemma 7.17"},{"comment":"Both Lemma 7.16 and Lemma 7.17 use the inference that v(T'')[1,z] >lex v(T')[1,z] implies ||v(T'')[1,z]||_1 > ||v(T')[1,z]||_1. Lexicographic order does not compare ℓ1-norms; for example, (2,0,0) is lexicographically larger than (1,1,1) while having a smaller ℓ1-norm. The subsequent conclusions that the width of T'' is at least 4t^2+t−1 and that there exists i1 < i with the required norm equality both depend on this norm inequality. As written, the minimality argument in both lemmas is therefore incomplete.","section":"§7, Lemmas 7.16 and 7.17"}],"minor_comments":[{"comment":"The displayed formula for f1.1(k) is typeset ambiguously; the tower of exponents should be parenthesized so that the expression matches the recurrence in Theorem 7.18.","section":"§1, Theorem 1.1 display"},{"comment":"In the proof of Lemma 2.2, the text refers to P' shortly after defining P* and Q*; this appears to be a typo for P*, and the notation should be made consistent.","section":"§2, Lemma 2.2"},{"comment":"The wording of Observation 9.1 is confusing about the direction of reachability: the definitions say w is weakly reachable from v, but the observation says 'v is strongly reachable from w'. Please align the notation with the definitions.","section":"§9, Observation 9.1"},{"comment":"The phrase 'the edges on P between the endpoints of Y4i−3 and X4i−1 are butterfly contractible' is terse; since P and Q have opposite orientations, it would help to state explicitly which endpoint of each rung is used in the contraction order.","section":"§4, Lemma 4.1"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the reader's report accepted the paper with moderate confidence, and much of the architecture is sound. My independent reading confirms the main structure and most of the auxiliary lemmas, but the two gaps in Section 7 are in the core refinement argument that leads to Theorem 1.1. They appear fixable, but they require non-local revision of Lemmas 7.16 and 7.17, and possibly of Lemma 7.6 or Lemma 7.4. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is very good, very long, and has a specific place where I think the proof has a hole. The main theorem — that large cycle rank forces one of three explicit butterfly minors — is exactly the result the digraph width community has been waiting for. The three families are natural, the pairwise independence in Section 8 is real, and Theorem 1.3 (cycle rank equals weak (∞,→)-coloring number minus one) is a clean new connection. The chain-decomposition machinery is elaborate and mostly carefully written.\n\nThe hole is in Lemma 7.17. The proof chooses a clean chain decomposition T′ minimizing i, then invokes Lemma 7.6. In outcome (2) of that lemma you only get a chain decomposition T′′ with larger full height and a lexicographically larger weight vector; nothing in outcome (2) says T′′ is clean. Yet the minimality contradiction at the end uses T′′ as if it were a clean decomposition. The construction of outcome (2) runs through Lemma 7.4, which definitely does not preserve cleanliness. So the contradiction cannot be drawn without an extra argument. This is not cosmetic: Lemma 7.17 is the only bridge from clean to spotless decompositions, and the spotless decomposition is what finally yields TC_k. If the gap is real, Theorem 1.1 currently lacks a proof.\n\nI also had a smaller worry about the step from lexicographic increase to increased sum in the same lemma. Lexicographic increase of the weight vector does not by itself force the sum of the first z entries to exceed the target. That may be fixable by a more careful accounting, but it is another place to check.\n\nEverything before Lemma 7.6 — the relaxed ladders, mixed chains, Lemma 4.4, the Erdős–Pósa argument in 7.1–7.2 — looked fine on my reading. Section 9 stands alone and is solid. If the gap is patched, this becomes a major structural result. As it stands, I would not cite the main theorem as proven, but I would happily cite Theorem 1.3 and the chain-decomposition framework. Send it to a careful referee willing to audit Section 7. It deserves referee time, not a desk reject.","headline":"Important result with a real-looking gap in Lemma 7.17: the bridge from clean to spotless decompositions may not hold as written.","tokens_in":52666,"tokens_out":7527,"would_cite":false,"duration_ms":79744,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every digraph whose cycle rank is large enough contains one of three explicit digraphs—a directed ladder, a directed cycle chain, or a directed tree chain—as a butterfly minor, and this yields an exact characterization of…","keywords":["cycle rank","butterfly minors","directed treewidth","directed grid theorem","weak coloring numbers","directed ladders","directed tree chains","treedepth"],"falsifier":"Exhibit, for some fixed $k$, a sequence of digraphs whose cycle rank is unbounded but none of which contains $L_k$, $CC_k$, or $TC_k$ as a butterfly minor. This would directly contradict Theorem 1.1. A less direct check is to construct a digraph with large directed treewidth but no large cylindrical grid butterfly minor, which would invalidate the proof's main reduction step.","tokens_in":1942,"feed_emoji":"🪜","tokens_out":2406,"duration_ms":96461,"temperature":0.7,"pith_summary":"Cycle rank is a depth measure for digraphs that dates back to 1963 and behaves like the digraph analogue of treedepth: acyclic digraphs have rank zero, strongly connected pieces contribute one more than the best vertex deletion, and components combine by taking the maximum. The paper proves that this parameter is governed by exactly three simple obstruction families: if a digraph's cycle rank is at least $f(k)$, then it must contain a directed ladder $L_k$, a directed cycle chain $CC_k$, or a directed tree chain $TC_k$ as a butterfly minor, where butterfly minor is the directed contraction operation that only identifies edges with a unique tail or a unique head. This is Theorem 1.1, and it implies Theorem 1.2: a class of digraphs closed under butterfly minors has bounded cycle rank if and only if it excludes all three families for some fixed $k$. The paper also proves an exact identity connecting cycle rank to a directed version of weak coloring numbers: the cycle rank equals the weak $(\\infty,\\to)$-coloring number minus one. The broader significance is that explicit unavoidable structures for digraph width parameters are rare, and a theorem of this kind turns high cycle rank into a substructure one can point to and certify.","feed_headline":"Large cycle rank forces one of three butterfly minors","feed_subtitle":"Butterfly-minor-closed digraph classes have bounded cycle rank exactly when they exclude all three families.","key_machinery":"The proof centers on chain decompositions of digraphs: a rooted binary tree whose root is the whole digraph, whose leaves are strongly connected digraphs, and in which every internal node's digraph is formed from its two children by a mixed link. A mixed link joins two 2-terminal strongly connected digraphs by a mixed chain, a sequence of relaxed ladders and paths that interpolates between a relaxed chain and a relaxed ladder; the weight of a mixed chain is its length plus the orders of its relaxed ladders. The decomposition is refined through two structural properties, called clean and spotless, and a spotless chain decomposition of height $k+3$ yields a relaxed tree chain of order $k$ as a butterfly minor. High directed treewidth is handled separately by the directed grid theorem: a digraph of large directed treewidth contains a large cylindrical grid, from which a cycle chain, and in order $2k$ a ladder, is extracted as a butterfly minor. The identity $\\mathrm{cr}(G)=\\mathrm{wcol}^{\\to}_{\\infty}(G)-1$ is proved by an induction that moves between cycle-rank decompositions and linear vertex orderings.","core_discovery":"The central claim, on the paper's own terms, is Theorem 1.1: there is a function $f_{1.1}:\\mathbb{N}\\to\\mathbb{N}$ such that for every positive integer $k$, every digraph of cycle rank at least $f_{1.1}(k)$ contains $L_k$, $CC_k$, or $TC_k$ as a butterfly minor. Here $L_k$ is a directed ladder (two directed paths of length $k$ joined by antiparallel rungs), $CC_k$ is a directed cycle chain (a path whose edges are replaced by 2-cycles), and $TC_k$ is a directed tree chain (built recursively from two copies of $TC_{k-1}$ linked by two crossing edges). A butterfly minor is obtained by deleting vertices and edges and by contracting only edges whose tail or head is unique. The paper establishes that each of the three families has unbounded cycle rank, that ladders and cycle chains appear inside large cylindrical grids, that tree chains do not, and that the three families are pairwise independent, so none is redundant. Theorem 1.2 follows: a butterfly-minor-closed class of digraphs has bounded cycle rank if and only if there is some $k$ such that it contains none of $L_k$, $CC_k$, $TC_k$. A separate theorem, Theorem 1.3, states the exact identity $\\mathrm{cr}(G)=\\mathrm{wcol}^{\\to}_{\\infty}(G)-1$ between cycle rank and the directed weak coloring number.","pith_inferences":["The proof is described as mostly constructive; if the remaining Erdős–Pósa step can be made fully algorithmic, the obstruction theorem would point toward a parameterized algorithm or approximation for cycle rank, a question the paper explicitly leaves open.","The equality with the weak $(\\infty,\\to)$-coloring number suggests that cycle rank can be understood through vertex orderings and directed reachability, potentially connecting it to directed notions of sparsity and bounded expansion.","The tower-type bound in $f_{1.1}$ is largely inherited from the directed grid theorem; the planar analogue already yields a double-exponential bound, so a grid-free proof of the same structural theorem would likely give a substantially smaller, and more usable, function."],"forward_implications":["For every butterfly-minor-closed class of digraphs, bounded cycle rank is equivalent to excluding all of $L_k$, $CC_k$, $TC_k$ for some fixed $k$.","Large cylindrical grids already force cycle chains, and order-$2k$ grids force ladders, so the only genuinely new obstruction supplied beyond the directed grid theorem is the tree chain, which is not a butterfly minor of any cylindrical grid.","The three obstruction families are pairwise independent: no family lies in the butterfly-minor closure of another, so all three are needed in Theorem 1.1.","Any digraph containing one of the three order-$k$ structures has cycle rank at least $\\lfloor\\log k\\rfloor$ for ladders and cycle chains, or at least $k$ for tree chains, and butterfly minors cannot raise cycle rank.","Cycle rank equals the weak $(\\infty,\\to)$-coloring number minus one, giving an ordering-based description that mirrors the classical treedepth/weak-coloring relationship for undirected graphs."],"supporting_citations":[{"why":"Provides the directed grid theorem used to force a cycle chain when directed treewidth is large, and otherwise lets the proof assume bounded directed treewidth.","marker":"[22]"},{"why":"Supplies the improved bound for the directed grid theorem that makes the stated function $f_{1.1}$ explicit rather than non-elementary.","marker":"[18]"},{"why":"Gives the exact cycle rank of directed cycle chains and the observation that vertex and edge deletion do not increase cycle rank, anchoring the lower bounds for the obstruction families.","marker":"[28]"},{"why":"Supplies the butterfly-minor model characterization through arborescence decompositions, used throughout the extraction arguments.","marker":"[2]"},{"why":"Provides the lacing lemma that turns arbitrary pairs of linking paths into laced pairs, a step used repeatedly in mixed-chain and chain-decomposition constructions.","marker":"[19]"},{"why":"Characterizes butterfly minors of cylindrical grids via dual dijoin paths, used to prove that tree chains are not butterfly minors of cylindrical grids and are therefore genuinely new obstructions.","marker":"[3]"}],"fun_headline_variants":["Cycle rank forces one of three butterfly minors","Butterfly-minor trio unavoidable at high cycle rank","Cycle rank: three unavoidable butterfly minors","Large cycle rank guarantees a butterfly minor trio","Butterfly minors: cycle rank forces a trio"],"cache_read_input_tokens":54784,"weakest_assumption_plain":"The proof leans on the directed grid theorem, which says that every digraph of sufficiently large directed treewidth contains a large cylindrical grid as a butterfly minor; if that theorem, or the concrete bound used for it, failed, the reduction from high cycle rank to bounded directed treewidth would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Cycle rank forces one of three butterfly minors","Butterfly-minor trio unavoidable at high cycle rank","Cycle rank: three unavoidable butterfly minors","Large cycle rank guarantees a butterfly minor trio","Butterfly minors: cycle rank forces a trio"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001218,"raw_usage":{"total_tokens":5002,"prompt_tokens":929,"completion_tokens":4073,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":4013}},"tokens_in":545,"tokens_out":4073,"duration_ms":34021,"temperature":1.0,"reasoning_tokens":4013,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:00:53.298203+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit, for some fixed $k$, a sequence of digraphs whose cycle rank is unbounded but none of which contains $L_k$, $CC_k$, or $TC_k$ as a butterfly minor. This would directly contradict Theorem 1.1. A less direct check is to construct a digraph with large directed treewidth but no large cylindrical grid butterfly minor, which would invalidate the proof's main reduction step.","supporting_citations":[{"cited_title":"The dire cted grid theorem","cited_arxiv_id":null,"evidence_quote":"Provides the directed grid theorem used to force a cycle chain when directed treewidth is large, and otherwise lets the proof assume bounded directed treewidth."},{"cited_title":"Cycles of Well- Linked Sets and an Elementary Bound for the Directed Grid The orem","cited_arxiv_id":null,"evidence_quote":"Supplies the improved bound for the directed grid theorem that makes the stated function $f_{1.1}$ explicit rather than non-elementary."},{"cited_title":"The loop complexity of regular even ts","cited_arxiv_id":null,"evidence_quote":"Gives the exact cycle rank of directed cycle chains and the observation that vertex and edge deletion do not increase cycle rank, anchoring the lower bounds for the obstruction families."},{"cited_title":"The Erdos-Posa Property for Directed Graphs","cited_arxiv_id":"1603.02504","evidence_quote":"Supplies the butterfly-minor model characterization through arborescence decompositions, used throughout the extraction arguments."},{"cited_title":"Generating strongly 2-connected digraphs","cited_arxiv_id":"2411.09791","evidence_quote":"Provides the lacing lemma that turns arbitrary pairs of linking paths into laced pairs, a step used repeatedly in mixed-chain and chain-decomposition constructions."},{"cited_title":"Decid- ing the Erd˝ os-P´ osa property in 3-connected digraphs","cited_arxiv_id":null,"evidence_quote":"Characterizes butterfly minors of cylindrical grids via dual dijoin paths, used to prove that tree chains are not butterfly minors of cylindrical grids and are therefore genuinely new obstructions."}],"review_version":1}