REVIEW 2 major objections 3 minor 11 references
Halin's grid theorem for digraphs
T0 review · 2 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Section 3, footnote 5 and Lemma 3.1] 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 7, Theorem 1.4] 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.
minor comments (3)
- [Section 3, proof of Lemma 3.1] 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 2, Proposition 2.4] 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 5, proof of Lemma 5.1] The notation 'j_1, . . . , j_n /∈ I_n' is a typesetting issue; it should read 'j_1, . . . , j_n ∉ I_n'.
Circularity Check
No significant circularity: the main theorem is proved from internal lemmas plus an independent prior classification; no fitted inputs or definitional identifications were found.
full rationale
The derivation chain of Theorem 1.2 is a sequence of graph-theoretic reductions (Lemmas 3.1, 4.1, 4.2, 5.1, and Claim 6.0.1) that are proved inside the paper. The only external input with overlapping authorship is Theorem 3.2, cited as [10, Corollary 1.4], which classifies the butterfly minors that occur in every infinite strongly connected digraph. This is a self-citation, but it is not circular: it is a parameter-free structural statement whose assumptions (infinite strong connectivity) do not include the target conclusion (existence of quarter-grid subdivisions with prescribed vertical rays), and the paper's main theorem is not used in proving it. The footnote in Section 3 highlights a possible mismatch between contraction-based and tree-like-model butterfly minors for infinite digraphs, but that is a soundness/completeness concern about whether [10] supplies the required model, not a reduction of the paper's conclusion to its own assumptions. Theorem 1.4's auxiliary contraction of necklaces to out-rays is likewise a construction rather than a renaming of the target result; any unproved preservation of disjointness is a potential gap, not circularity. No fitted parameters, no self-definitional equivalences, and no known results repackaged under new names were found.
Assumptions & free parameters
assumptions (3)
- domain assumption Every infinite strongly connected digraph contains a butterfly minor among D(K_{1,infty}), D(S) for an undirected ray S, or a dominated directed ray.
- ad hoc to paper Contraction of necklace parts in Section 7 preserves enough of the disjoint-path structure to make the resulting out-rays equivalent.
- standard math Countable reduction: any infinite family of disjoint rays in the statement can be replaced by a countably infinite subfamily.
Cite this review
Pith. "Pith review of Halin's grid theorem for digraphs." pith.science (2026). https://pith.science/paper/7YLUHRKY
@misc{pith2026241203482,
author = {Pith},
title = {Pith review of: Halin's grid theorem for digraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/7YLUHRKY}},
note = {Machine review of arXiv:2412.03482}
}
abstract
Halin showed that every thick end of every graph contains an infinite grid. We extend Halin's theorem to digraphs. More precisely, we show that for every infinite family $\mathcal{R}$ of disjoint equivalent out-rays there is a grid whose vertical rays are contained in $\mathcal{R}$. Furthermore, we obtain similar results for in-rays and necklaces.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[7]
M. Hamann and K. Heuer,Infinite grids in digraphs, arXiv preprint arXiv:2412.03302 (2024)
arXiv 2024
-
[10]
A star-comb lemma for infinite digraphs
F. Reich,A star-comb lemma for infinite digraphs, arXiv preprint arXiv:2406.04877 (2024)
work page Pith review arXiv 2024
-
[1]
S. A. Amiri, K.-i. Kawarabayashi, S. Kreutzer, and P. Wollan,The Erd˝ os-P´ osa Property for directed graphs, arXiv preprint arXiv:1603.02504 (2016)
arXiv 2016
-
[2]
N. Bowler and F. Reich,Connectoids I: a universal end space theory, arXiv preprint arXiv:2405.14704 (2024)
arXiv 2024
-
[3]
Ends of digraphs I: basic theory
C. B¨ urger and R. Melcher,Ends of digraphs I: basic theory, arXiv preprint arXiv:2009.03295 (2020)
work page Pith review arXiv 2020
-
[4]
Diestel,Graph Theory, 6th ed., Springer (print edition); Reinhard Diestel (eBooks), 2024
R. Diestel,Graph Theory, 6th ed., Springer (print edition); Reinhard Diestel (eBooks), 2024
work page 2024
-
[5]
A. Georgakopoulos and M. Hamann,A full Halin grid theorem, Discrete & Computational Geometry (2024), 1–13
work page 2024
-
[6]
R. Halin, ¨Uber die Maximalzahl fremder unendlicher Wege in Graphen, Mathematische Nachrichten30 (1965), no. 1-2, 63–85
work page 1965
Show all 11 references
-
[8]
Heuer,Excluding a full grid minor, Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg, 2017, pp
K. Heuer,Excluding a full grid minor, Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg, 2017, pp. 265–274
2017
-
[9]
Kurkofka, R
J. Kurkofka, R. Melcher, and M. Pitz,A strengthening of Halin ’s grid theorem, Mathematika68(2022), no. 4, 1009–1013
2022
-
[11]
Zuther,Ends in digraphs, Discrete mathematics184(1998), no
J. Zuther,Ends in digraphs, Discrete mathematics184(1998), no. 1-3, 225–244. Universit¨at Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Ham- burg, Germany Email address:florian.reich@uni-hamburg.de
1998
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.