{"id":"d48d9114-58b7-434e-a99d-d192ca3f0182","arxiv_id":"2412.03482","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every infinite family of disjoint equivalent directed rays in a digraph contains a directed quarter-grid with those rays as vertical rays, with an analogous result for necklace-based ends.","lead":"This paper proves a directed version of Halin's grid theorem: any infinite family of equivalent, disjoint out-rays in a digraph contains a subdivision of a quarter-grid whose vertical rays are exactly the given family. It also gives the same result for in-rays and for necklace-based ends, identifying two grid types that are both necessary and sufficient.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1 depends on [10, Cor. 1.4] producing tree-like butterfly minors, but the paper's own footnote says the contraction-based notion is more inclusive for infinite digraphs; if [10] proves only that weaker guarantee, the key case of Theorem 1.2 is unsupported.","rationale":"After reading the full proof, the structural arguments in Sections 4–6 and the necklace reduction in Section 7 are coherent, and I found no direct internal contradiction; the recursive constructions respect the required avoidance conditions. The weakest point is the import of Theorem 3.2, not because it is a preprint, but because the manuscript itself flags a definitional discrepancy between infinite butterfly minors obtained by contractions and the tree-like models needed in Lemma 3.1. If [10] proves its corollary for the more inclusive contraction-based notion, then the guarantee used here may be strictly stronger than what is available; in that case Lemma 3.1 collapses, and with it the proof of Theorem 1.2, since all other lemmas ultimately route to Lemma 3.1. The proposed check is a targeted verification of that single classification in the exact definition used, which would settle the concern. I therefore keep the reader's conditional verdict: the paper should be accepted only after this dependency is confirmed or the proof of Theorem 3.2 is included.","tokens_in":19195,"tokens_out":39009,"duration_ms":387469,"concrete_test":"Inspect [10, Cor. 1.4] and its proof to identify whether the butterfly minor is constructed as a tree-like model (with the root/reachability property used here) or via contraction sequences as relaxed in the footnote. If the latter, attempt to refine the three models (D(K_{1,∞}), D(S), dominated directed ray) to tree-like models in any infinite strongly connected digraph; equivalently, search for a strongly connected digraph that has a contraction-based butterfly minor of one of the three types but no tree-like-model butterfly minor. This determines whether Lemma 3.1's application of Theorem 3.2 is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.2 is reduced, via Lemma 5.1 and Claim 6.0.1, to Lemma 3.1, whose first step applies Theorem 3.2 to an infinite strong component C of D∞(I). Lemma 3.1 then turns each edge of the butterfly minor M into a σ(u)–σ(v) path in D∞(I) and finally into infinitely many disjoint R_u–R_v paths in D. This requires M to be realized by a tree-like model: each branch set µ(v) needs a common root that can reach every leaving edge and be reached from every entering edge. The paper's own footnote in Section 3 concedes that, for infinite digraphs, the standard contraction-sequence definition of butterfly minors is more general than the tree-like-model definition used here: the branch set may lack such a root. If [10, Cor. 1.4] was proved for the contraction-based notion only, then Theorem 3.2 as stated is not established, and the recursive grid construction in Lemma 3.1 has no basis. There is no fallback if the classification has a missing case or if the produced models are not tree-like. Because Claim 6.0.1 makes D∞(I4) strongly connected precisely in order to invoke Lemma 3.1, this is the single load-bearing step of the main theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a directed analogue of Halin's grid theorem. Theorem 1.2 states that for every infinite family of disjoint equivalent out-rays (or in-rays) in a digraph D, there exists a subdivision of either a bidirected quarter-grid or a cyclic quarter-grid (or their reverses) whose vertical rays are exactly the given family. Theorem 1.3 weakens the conclusion to vertical rays equivalent to the given family, and Theorem 1.4 transfers the result to families of disjoint necklaces, yielding bidirected or cyclic necklace grids. The proof of Theorem 1.2 is structured around the auxiliary digraph D∞(I) obtained from the ray family; Sections 3 and 4 handle the cases where D∞(I) has an infinite strong component or an in-/out-ray, Section 5 constructs suitable subfamilies and staircase paths, and Section 6 combines these to force a strongly connected auxiliary graph and applies Lemma 3.1. Section 7 reduces the necklace theorem to Theorem 1.2 via an auxiliary strong minor. The paper is well-written and the combinatorial constructions are intricate.","tokens_in":19510,"tokens_out":16118,"duration_ms":138329,"significance":"If the main theorem is correct, it is a substantial contribution to infinite digraph theory: it extends Halin's classical grid theorem to Zuther ends of digraphs and shows exactly which grid types are necessary and sufficient. The result also yields a necklace version via a clever auxiliary-minor reduction. The paper is largely self-contained, with original Lemmas (5.1, 5.4, Claim 6.0.1) and a clear organisation. The main caveat is the reliance on an imported classification theorem whose exact definitional form is in question.","major_comments":[{"comment":"The proof of Lemma 3.1 invokes Theorem 3.2 to obtain, from an infinite strongly connected component C of D∞(I), a butterfly minor M that is D(K_{1,∞}), D(S) or a dominated directed ray, and then uses a tree-like model µ of M in which each branch set µ(v) has a common root σ(v) that can reach all outgoing edges and be reached from all incoming edges. The footnote on page 5, however, states that for infinite digraphs the contraction-sequence definition of butterfly minors is more general than the tree-like-model definition used here, and that in the more general setting a branch set may have no such root (citing [10, Section 2.4]). If [10, Corollary 1.4] is proved only for the more general contraction-based notion, then Theorem 3.2 as stated is not established, and the recursive grid construction in Lemma 3.1 (which routes paths through the common roots σ(v)) is unsupported. This is the load-bearing step of Theorem 1.2, as Claim 6.0.1 is designed precisely to put the argument into the setting of Lemma 3.1. Please clarify which notion [10, Corollary 1.4] applies to, and if it is only the contraction-based notion, provide either a proof of the tree-like version or an adaptation of Lemma 3.1 that does not require a common root in every branch set.","section":"Section 3, footnote 5 and Lemma 3.1"},{"comment":"The reduction from necklaces to rays relies on two assertions that are stated without proof: (i) the set α(N) is infinite and satisfies |α(n,N)-α(m,N)| ≥ 2 for n≠m, and (ii) every two disjoint paths in the auxiliary digraph A expand to disjoint subgraphs of D. The first assertion is not immediate from the recursive definition of α(n,N) and the choice of P_n, and the second is crucial because the expansion involves contracting strong components of the necklaces, so two paths that are disjoint in A could conceivably meet inside a contracted component. Since these facts are what make the application of Theorem 1.2 to A produce a valid necklace grid in D, the proof of Theorem 1.4 is incomplete as written. Please give a detailed proof of both assertions.","section":"Section 7, Theorem 1.4"}],"minor_comments":[{"comment":"The statement 'This implies that there are infinitely many disjoint R_{σ(v)}–R_{σ(w)} paths' is not immediate; it should be justified by iterating Proposition 2.3 with finite forbidden sets consisting of previously chosen paths and the finite set of roots σ(x).","section":"Section 3, proof of Lemma 3.1"},{"comment":"There is a typo in the sentence 'There does not exists an n∈N'; it should be 'There does not exist an n∈N'.","section":"Section 2, Proposition 2.4"},{"comment":"The notation 'j_1, . . . , j_n /∈ I_n' is a typesetting issue; it should read 'j_1, . . . , j_n ∉ I_n'.","section":"Section 5, proof of Lemma 5.1"}],"recommendation":"major_revision","confidential_remarks":"The main risk to the paper is the unclarity around the exact form of [10, Corollary 1.4]. Since the paper's own footnote signals that the contraction-based definition is more general for infinite digraphs, the author should be asked to state precisely which definition [10] uses and to bridge the gap. The necklace theorem also needs a more detailed proof of the expansion/disjointness step. If those points are resolved, the paper would be a strong contribution. The reader's report's stress-test concern about the tree-like model is legitimate and should be taken seriously."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Florian's paper proves the directed version of Halin's grid theorem: any infinite family of disjoint equivalent out-rays (or in-rays) contains a subdivision of a bidirected or cyclic quarter-grid with the given rays as vertical rays. That is a real strengthening of the recent Hamann-Heuer result [7], which only gets the bidirected grid with vertical rays equivalent to the given family, and it also beats Zuther's special case. The necklace variant, Theorem 1.4, is new too, and the two grid types are shown necessary. The proof follows the Kurkofka-Melcher-Pitz strategy but has to handle directed complications, and the author does a careful job of setting up the auxiliary digraphs D(J) and D∞(J). I found no direct contradiction and the case split (Sections 3-5) looks complete.\n\nThe main soft spot is the use of [10, Corollary 1.4], imported from the author's own preprint, as the starting classification for infinite strongly connected digraphs. Lemma 3.1 needs a tree-like butterfly minor: each branch set must have a common root that can reach all leaving edges and be reached from all entering edges. The paper's own footnote concedes that the contraction-sequence definition of butterfly minor is more inclusive in the infinite case and can lack such a root. So everything hinges on whether [10] actually proves the tree-like version. If it proves only the contraction-based version, Theorem 3.2 as stated is not established and Lemma 3.1 collapses at its first case. I could not check [10] from this manuscript; a referee should verify this explicitly.\n\nA smaller point: in Theorem 1.4, the reduction to out-rays compresses the claim that disjoint paths in the auxiliary digraph expand to disjoint subgraphs in the original. That is stated rather than proved. It looks plausible given the α(N) spacing, but it deserves a few sentences.\n\nThe paper is well written, credits the concurrent work honestly, and the constructions are convincing at the level of detail typical for this area. The hard dependency on [10] is the one reason I would not sign off on it without referee verification.\n\nRecommendation: send it to peer review. It is a significant result for infinite digraph theory, and a good referee can check the [10] dependency and ask for the necklace-to-ray details. I would bring it to our reading group.","headline":"A genuine extension of Halin's grid theorem to digraphs, with a proof that is mostly convincing but leans on a black-box butterfly-minor classification that deserves referee scrutiny.","tokens_in":20015,"tokens_out":5066,"would_cite":true,"duration_ms":46111,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C63","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every infinite family of disjoint equivalent out-rays in a digraph forces a subdivision of either a bidirected or a cyclic quarter-grid whose vertical rays come from that family.","keywords":["Halin grid theorem","infinite digraph","thick end","out-ray","in-ray","quarter-grid","necklace","butterfly minor"],"falsifier":"A direct falsifier would be an infinite family of pairwise disjoint equivalent out-rays in a digraph that contains no subdivision of a bidirected or cyclic quarter-grid whose vertical rays belong to the family; the proof predicts that every such family yields an auxiliary digraph $D^\\infty(J)$ with an infinite strong component, an in-ray, or an out-ray, so searching for a counterexample can be reduced to computing $D^\\infty(J)$ for candidate families.","tokens_in":18995,"feed_emoji":"🕸️","tokens_out":10238,"duration_ms":91161,"temperature":0.7,"pith_summary":"This paper proves a directed version of Halin's grid theorem: in any digraph, an infinite family of pairwise disjoint equivalent out-rays (or in-rays) forces a subdivision of one of two explicitly described quarter-grids, with the original rays as its vertical rays. The two grid types—the bidirected quarter-grid and the cyclic quarter-grid, with reversed versions for in-rays—are exactly the unavoidable witnesses for thick directed ends, and neither type can be replaced by the other. The paper also obtains a relaxed form in which the vertical rays only need to be equivalent to the given family and the grid is always the bidirected quarter-grid, and it extends the dichotomy from rays to necklaces, the strongly connected subgraphs used to build directed ends. A reader should take away that thick directed ends are pinned down by two concrete, mutually non-interchangeable grid shapes.","feed_headline":"Every thick digraph end hides a quarter-grid","feed_subtitle":"Halin's grid theorem extends to directed rays and necklaces, with exactly two grid shapes doing the work.","key_machinery":"The proof's engine is an auxiliary digraph built from the given rays. One fixes an out-ray $S$ that meets every $R_i$ infinitely often; for any subfamily $J$, the digraph $D(J)$ is obtained by contracting each $R_i$ ($i \\in J$) to a single vertex, suppressing vertices of in- and out-degree one, and deleting loops, and $D^\\infty(J)$ keeps only the edges of $D(J)$ that occur with infinite multiplicity. The paper defines 'staircases,' directed paths that hop through prescribed rays in a specified order, and uses them to build the grid's 'girders' connecting the vertical rays. If some $D^\\infty(J)$ has an infinite strong component, an in-ray, or an out-ray, a quarter-grid is read off from a butterfly-minor model—a small digraph embedded via disjoint in- and out-arborescences—whose existence the paper imports for infinite strongly connected digraphs. In the remaining case, two lemmas construct families of disjoint ray-to-ray paths respecting a linear order and weave them into a strongly connected $D^\\infty(I_4)$, which triggers the first case and completes the grid.","core_discovery":"The central claim, Theorem 1.2, is that for every infinite family $(R_i)_{i \\in I}$ of pairwise disjoint equivalent out-rays (or in-rays) in a digraph $D$ there exists a subdivision $D'$ of either a (reversed) bidirected quarter-grid or a (reversed) cyclic quarter-grid in $D$ such that each vertical ray of $D'$ is an element of the given family. Since every out-ray inside either grid is equivalent to every other, the subdivision witnesses that the corresponding directed end is thick, and the theorem says that every thick end with a prescribed infinite family of disjoint equivalent rays must contain one of these two grids with exactly those rays as its vertical rays. The paper further shows that the two grid types are jointly necessary (each grid type avoids the other), proves a relaxed version in which the vertical rays only need to be equivalent to the given family and the grid is always a bidirected quarter-grid, and proves an analogous necklace version for thick ends formed by strongly connected subgraphs.","pith_inferences":["This dichotomy suggests that thick directed ends come in two orientational flavours, one where consecutive rays are mutually reachable and one where all rays reach back to a common first ray; classifying which digraphs force each flavour would sharpen the theorem.","The auxiliary-digraph technique, keeping only edges of infinite multiplicity after contracting rays, looks reusable for other equivalence notions on directed paths, such as ends of relatives or tree-decompositions of digraphs.","A natural next step, by analogy with the undirected full-Halin theorem, is to ask when a thick directed end contains the full quarter-grid (not just a subdivision) as a subgraph; the paper's constructions produce subdivisions, and the gap between subdivision and full containment is where obstruction examples would live.","The necklace theorem's contraction step — turning necklaces into out-rays while preserving disjoint path structure — could be made into a general translation principle between strongly connected subgraphs and rays, which would let ray-theoretic grid theorems be exported to other connectivity-based end theories."],"forward_implications":["Every thick directed end is witnessed by a subdivision of the bidirected or the cyclic quarter-grid whose vertical rays are exactly the members of any prescribed infinite family of disjoint equivalent rays.","Because each grid contains only equivalent rays, the witnessing grid itself is a self-contained certificate that the end is thick, not just an abstract existence statement.","Relaxing the vertical-ray condition still forces a bidirected quarter-grid, so the bidirected grid is the universal relaxed witness shape.","The necklace version shows the same dichotomy holds for thick ends of strongly connected digraphs: each such end contains either a bidirected or a cyclic necklace grid with prescribed vertical necklaces.","Neither grid type can be dropped: the bidirected and cyclic grids are mutually non-containing, and the same mutual non-containment persists for necklace grids even under the relaxed condition."],"supporting_citations":[{"why":"Supplies the butterfly-minor trichotomy for infinite strongly connected digraphs that starts the proof of Lemma 3.1.","marker":"[10, Corollary 1.4]"},{"why":"Provides the strengthening of Halin's theorem and the method of contracting rays to an auxiliary digraph that the paper adapts.","marker":"[9]"},{"why":"The original Halin grid theorem for undirected graphs that the paper extends to digraphs.","marker":"[6]"},{"why":"Defines equivalence of in- and out-rays and directed ends, and proves a special case of the relaxed bidirected-grid statement.","marker":"[11]"},{"why":"Independently proves the relaxed bidirected-quarter-grid theorem (Theorem 1.3) and supplies an alternative notion of the cyclic quarter-grid.","marker":"[7]"},{"why":"Introduces necklaces as the objects whose thick ends are treated in Theorem 1.4.","marker":"[3]"},{"why":"Provides the definition of necklace (via finite strongly connected witnesses) that Theorem 1.4 relies on.","marker":"[2]"}],"fun_headline_variants":["Halin's grid theorem now applies to digraphs","Every thick digraph end contains a quarter-grid","Two grid shapes prove Halin's theorem for digraphs","Thick digraph ends always host a Halin grid"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on the imported classification that every infinite strongly connected digraph contains one of three butterfly minors (a bidirectional infinite star, a bidirectional ray, or a dominated directed ray), and separately on the unproved assumption that contracting necklace pieces in the auxiliary digraph preserves enough disjointness to produce equivalent out-rays.","fun_headline_variants_meta":{"raw":{"variants":["Halin's grid theorem now applies to digraphs","Every thick digraph end contains a quarter-grid","Two grid shapes prove Halin's theorem for digraphs","Thick digraph ends always host a Halin grid"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000296,"raw_usage":{"total_tokens":1642,"prompt_tokens":791,"completion_tokens":851,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":407,"completion_tokens_details":{"reasoning_tokens":785}},"tokens_in":407,"tokens_out":851,"duration_ms":8416,"temperature":1.0,"reasoning_tokens":785,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:22:15.963949+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct falsifier would be an infinite family of pairwise disjoint equivalent out-rays in a digraph that contains no subdivision of a bidirected or cyclic quarter-grid whose vertical rays belong to the family; the proof predicts that every such family yields an auxiliary digraph $D^\\infty(J)$ with an infinite strong component, an in-ray, or an out-ray, so searching for a counterexample can be reduced to computing $D^\\infty(J)$ for candidate families.","supporting_citations":[{"cited_title":"Kurkofka, R","cited_arxiv_id":null,"evidence_quote":"Provides the strengthening of Halin's theorem and the method of contracting rays to an auxiliary digraph that the paper adapts."},{"cited_title":"Halin, ¨Uber die Maximalzahl fremder unendlicher Wege in Graphen, Mathematische Nachrichten30 (1965), no","cited_arxiv_id":null,"evidence_quote":"The original Halin grid theorem for undirected graphs that the paper extends to digraphs."},{"cited_title":"Ends of digraphs I: basic theory","cited_arxiv_id":"2009.03295","evidence_quote":"Introduces necklaces as the objects whose thick ends are treated in Theorem 1.4."}],"review_version":1}