pith. machine review for the scientific record. sign in

arxiv: 2605.07468 · v1 · submitted 2026-05-08 · 💻 cs.DM · math.CO

Recognition: 2 theorem links

· Lean Theorem

Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width

Dario Cavallaro , Ken-ichi Kawarabayashi , Stephan Kreutzer
Authors on Pith no claims yet

Pith reviewed 2026-05-11 02:20 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords well-quasi-orderingEulerian digraphsstrong immersioncarving widthtreewidthdirected graphsimmersionmeta-theorem
0
0 comments X

The pith

Every class of Eulerian directed graphs with bounded carving width is well-quasi-ordered by strong immersion.

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

The paper sets out to show that Eulerian digraphs whose carving width is bounded form well-quasi-ordered classes under strong immersion. This ordering property means any infinite sequence of such graphs must contain one that immerses into a later one, ruling out infinite antichains. The claim is strengthened to cover graphs whose vertices carry labels from any well-quasi-order, whose incident edges are linearly ordered at each vertex, and whose vertices may forbid certain path routings through them. A general framework is introduced that appears designed to establish well-quasi-ordering results for Eulerian digraphs under these strengthened conditions. The authors also record that the property fails when degree is unbounded, even if treewidth stays at most two, and they give a restricted class where weak immersion succeeds but strong immersion does not.

Core claim

We prove that every class of Eulerian directed graphs of bounded carving width is well-quasi-ordered by strong immersion. In fact we prove a stronger result, namely that every class of Eulerian directed graphs of bounded carving width, where every vertex is additionally labeled from a well-quasi-order, fixes a linear order on its incident edges, and may impose further restrictions on how the immersion is allowed to route paths through it, is well-quasi-ordered by an adequate notion of strong immersion. To this extent we develop a framework seemingly suited to prove well-quasi-ordering for classes of Eulerian directed graphs by (strong) immersion and present a first meta theorem in that way.

What carries the argument

A framework that reduces well-quasi-ordering questions for Eulerian digraphs to properties preserved under strong immersion when carving width is bounded.

If this is right

  • Any such bounded-carving-width class admits only finitely many minimal elements under strong immersion.
  • The same ordering holds when vertices receive labels from an arbitrary well-quasi-order and when linear orders on incident edges are fixed.
  • Routing restrictions at vertices can be added without destroying the well-quasi-ordering property.
  • The result fails for Eulerian digraphs of unbounded degree even when treewidth is at most two.
  • Certain restricted unbounded-degree classes are well-quasi-ordered by weak immersion but not by strong immersion.

Where Pith is reading between the lines

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

  • The framework may supply a template for proving analogous ordering results for other width-bounded classes of directed graphs.
  • The distinction drawn between strong and weak immersion suggests that algorithmic questions about immersion containment will behave differently depending on which notion is used.
  • Finite obstruction sets implied by the ordering could support fixed-parameter algorithms for immersion problems restricted to bounded carving width.

Load-bearing premise

An adequate definition of strong immersion exists that respects vertex labels, linear edge orders, and arbitrary routing restrictions while still letting the well-quasi-ordering property follow from the framework.

What would settle it

An infinite sequence of Eulerian digraphs, all of bounded carving width, whose members are pairwise incomparable under the paper's notion of strong immersion would show the central claim false.

Figures

Figures reproduced from arXiv: 2605.07468 by Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer.

Figure 1
Figure 1. Figure 1: An infinite antichain of Eulerian digraphs [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A schematic representation of how to reroute Euler-covers at well-linked vertices. The left [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Construction in proof of Theorem 3.25. L1 is marked in blue and L2 is marked in red. In particular there is no analogue to Theorem 2.8, and loosening the Theorem 2.12 to non-linear paths is crucial. Complementing the above remark, we have the following. Lemma 3.25. 1. Let Ω be a well-quasi-order. There exists a well-linked Ω-knitwork G with a strong mG-respecting linkage L of order 2 such that there exists… view at source ↗
Figure 4
Figure 4. Figure 4: Down- and Up-Stitching. Figure a) depicts a clamped graph G¯ = (G, π, X) with a rooted cut induced by Y , a choice of π(X) highlighted by a dotted oriented arrow, and a highlighted edge that is part of ρ(X)∩ρ(Y ). Figure b) depicts the down-stitch of G¯ and Y with down-stitch vertex y⋆. Figure c) depicts the up-stitch of G¯ and Y with up-stitch vertex y ⋆ fixing new roots πGY (y ∗ ) on ρ(y ∗ ), highlighted… view at source ↗
Figure 5
Figure 5. Figure 5: An example of a Torso with respective Pieces. Figure [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗
read the original abstract

We prove that every class of Eulerian directed graphs of bounded carving width (equivalently of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we prove a stronger result, namely that every class of Eulerian directed graphs of bounded carving width, where every vertex is additionally labeled from a well-quasi-order, fixes a linear order on its incident edges, and may impose further restrictions on how the immersion is allowed to route paths through it, is well-quasi-ordered by an adequate notion of strong immersion. To this extent, we develop a framework seemingly suited to prove well-quasi-ordering for classes of Eulerian directed graphs by (strong) immersion and present a first meta theorem in that direction. We complement our results by observing that the class of Eulerian directed graphs of unbounded degree is \emph{not} well-quasi-ordered by \emph{strong} immersion, even if we assume the treewidth of the class to be at most two. We conclude with a dichotomy result, proving for a very restricted class of Eulerian directed graphs of unbounded degree that it is not well-quasi-ordered by strong immersion, but it is well-quasi-ordered by weak immersion.

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 that every class of Eulerian directed graphs of bounded carving width (equivalently, bounded degree and treewidth) is well-quasi-ordered by strong immersion. It establishes a stronger meta-theorem for classes where vertices carry labels from a WQO, incident edges have fixed linear orders, and vertices may impose arbitrary routing restrictions on immersions; the proof proceeds via a developed framework for WQO results on Eulerian digraphs under (strong) immersion. Complementary results show that unbounded-degree Eulerian digraphs are not WQO under strong immersion even at treewidth 2, and a weak-vs-strong immersion dichotomy holds for a restricted unbounded-degree subclass.

Significance. If the central claims hold, the work supplies one of the first meta-theorems for well-quasi-ordering of Eulerian digraphs under immersion, extending the landscape beyond undirected graphs and other orders. The framework for handling labels, edge orders, and vertex-specific restrictions is reusable and the negative results delineate the precise role of bounded carving width. The manuscript ships a self-contained proof structure together with explicit counter-examples, which strengthens its contribution to the field.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'an adequate notion of strong immersion' is introduced without a forward pointer to its formal definition (presumably in the framework section); adding a one-sentence gloss or section reference would aid readers.
  2. [Introduction / main theorem statement] The equivalence 'bounded carving width (equivalently of bounded degree and treewidth)' is stated without a citation or short justification; a reference to the relevant lemma or standard fact would prevent any ambiguity for readers outside the immediate sub-area.
  3. [Dichotomy section] The final dichotomy result is presented concisely; a brief remark on whether the weak-immersion WQO extends to the labeled/ordered setting of the main theorem would clarify the scope of the positive results.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition of its significance as one of the first meta-theorems for well-quasi-ordering Eulerian digraphs under strong immersion, and the recommendation for minor revision. The report accurately captures the main contributions, including the framework for handling labels, edge orders, and vertex restrictions, as well as the complementary negative results on unbounded-degree classes.

Circularity Check

0 steps flagged

No significant circularity in the proof structure

full rationale

The manuscript presents a direct mathematical proof of a meta-theorem establishing well-quasi-ordering for Eulerian digraphs of bounded carving width under strong immersion, including strengthened versions with vertex labels, edge orders, and routing restrictions. No equations, fitted parameters, or self-referential definitions appear; the derivation relies on a developed framework of standard graph-theoretic techniques for WQO results rather than reducing any central claim to its own inputs by construction. Complementary negative results and a weak-vs-strong dichotomy are stated separately without circular dependence. The argument is self-contained against external benchmarks in graph theory and does not invoke load-bearing self-citations or ansatzes smuggled from prior work by the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard axioms from order theory and graph theory; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Well-quasi-orders are closed under finite products and certain relational constructions
    The stronger result with vertex labels and edge orders relies on known closure properties of well-quasi-orders.
  • domain assumption Eulerian digraphs satisfy equal in-degree and out-degree at every vertex
    This is the defining property of the graph class under consideration.

pith-pipeline@v0.9.0 · 5524 in / 1527 out tokens · 82048 ms · 2026-05-11T02:20:34.177050+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Classes of Directed Graphs

    J rgen Bang-Jensen and Gregory Gutin, editors. Classes of Directed Graphs . Springer Monographs in Mathematics . Springer International Publishing, Cham, 2018. https://doi.org/10.1007/978-3-319-71840-8 doi:10.1007/978-3-319-71840-8

    work page doi:10.1007/978-3-319-71840-8 2018

  2. [2]

    On embedding graphs in trees

    Dan Bienstock. On embedding graphs in trees. Journal of Combinatorial Theory, Series B , 49(1):103--136, 1990

    work page 1990

  3. [3]

    Strong immersion is a well-quasi-ordering for semicomplete digraphs

    Florian Barbero, Christophe Paul, and Micha Pilipczuk. Strong immersion is a well-quasi-ordering for semicomplete digraphs. Journal of Graph Theory , 90(4):484--496, April 2019. https://doi.org/10.1002/jgt.22408 doi:10.1002/jgt.22408

    work page doi:10.1002/jgt.22408 2019

  4. [4]

    Edge-disjoint paths in eulerian digraphs

    Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Edge-disjoint paths in eulerian digraphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 704--715, 2024

    work page 2024

  5. [5]

    A well-quasi-order for tournaments

    Maria Chudnovsky and Paul Seymour. A well-quasi-order for tournaments. Journal of Combinatorial Theory, Series B , 101(1):47--53, 2011

    work page 2011

  6. [6]

    Computing pivot-minors

    Konrad K Dabrowski, Fran c ois Dross, Jisu Jeong, Mamadou Moustapha Kant \'e , O-joung Kwon, Sang-il Oum, Dani \"e l Paulusma, et al. Computing pivot-minors. arXiv preprint arXiv:2311.04656 , 2023

    work page arXiv 2023

  7. [7]

    The complexity of the vertex-minor problem

    Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. The complexity of the vertex-minor problem. Information Processing Letters , 175:106222, 2022

    work page 2022

  8. [8]

    R. Diestel. Graph Theory . Springer, Heidelberg, 2017. https://doi.org/10.1007/978-3-662-53622-3 doi:10.1007/978-3-662-53622-3

    work page doi:10.1007/978-3-662-53622-3 2017

  9. [9]

    Well quasi-orders and regular languages

    Aldo de Luca and Stefano Varricchio. Well quasi-orders and regular languages. Acta Informatica , 31:539--557, 1994

    work page 1994

  10. [10]

    Two arc disjoint paths in Eulerian digraphs

    Andr \'a s Frank, Toshihide Ibaraki, and Hiroshi Nagamochi. Two arc disjoint paths in Eulerian digraphs. In Algorithms and Computations ( ISAAC ) , volume 1004, pages 92--101, Berlin, Heidelberg , 1995. Springer Berlin Heidelberg . https://doi.org/10.1007/BFb0015412 doi:10.1007/BFb0015412

    work page doi:10.1007/bfb0015412 1995

  11. [11]

    Connectivity and network flows

    Andr \'a s Frank. Connectivity and network flows. Handbook of combinatorics , 1:111--177, 1995

    work page 1995

  12. [12]

    Branch-width and well-quasi-ordering in matroids and graphs

    James F Geelen, Albertus MH Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. Journal of Combinatorial Theory, Series B , 84(2):270--290, 2002

    work page 2002

  13. [13]

    Ordering by Divisibility in Abstract Algebras

    Graham Higman. Ordering by Divisibility in Abstract Algebras . Proc. of the London Mathematical Society , 2(3), 1952

    work page 1952

  14. [14]

    The disjoint paths problem in quadratic time

    Ken ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B , 102(2):424--435, 2012. URL: https://www.sciencedirect.com/science/article/pii/S0095895611000712, https://doi.org/10.1016/j.jctb.2011.07.004 doi:10.1016/j.jctb.2011.07.004

    work page doi:10.1016/j.jctb.2011.07.004 2012

  15. [15]

    Eulerian digraph immersion

    Carl Darwin Thor Johnson. Eulerian digraph immersion . Princeton University, 2002

    work page 2002

  16. [16]

    Directed tree-width

    Thor Johnson, Neil Robertson, Paul D Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B , 82(1):138--154, 2001

    work page 2001

  17. [17]

    Vertex-minors of graphs: A survey

    Donggyu Kim and Sang-il Oum. Vertex-minors of graphs: A survey. Discrete Applied Mathematics , 351:54--73, 2024

    work page 2024

  18. [18]

    Minor containment and disjoint paths in almost-linear time

    Tuukka Korhonen, Micha Pilipczuk, and Giannos Stamoulis. Minor containment and disjoint paths in almost-linear time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 53--61. IEEE, 2024

    work page 2024

  19. [19]

    Well-quasi-ordering, the tree theorem, and vazsonyi's conjecture

    Joseph B Kruskal. Well-quasi-ordering, the tree theorem, and vazsonyi's conjecture. Transactions of the American Mathematical Society , 95(2):210--225, 1960

    work page 1960

  20. [20]

    The theory of well-quasi-ordering: A frequently discovered concept

    Joseph B Kruskal. The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A , 13(3):297--305, 1972

    work page 1972

  21. [21]

    Directed nowhere dense classes of graphs

    Stephan Kreutzer and Siamak Tazari. Directed nowhere dense classes of graphs. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , SODA 2012, Kyoto , Japan , January 17-19, 2012 , pages 1552--1562. SIAM, 2012. https://doi.org/10.1137/1.9781611973099.123 doi:10.1137/1.9781611973099.123

    work page doi:10.1137/1.9781611973099.123 2012

  22. [22]

    Recent progress on well-quasi-ordering graphs

    Chun-Hung Liu. Recent progress on well-quasi-ordering graphs. Well-Quasi Orders in Computation, Logic, Language and Reasoning: A Unifying Concept of Proof Theory, Automata Theory, Formal Languages and Descriptive Set Theory , pages 161--188, 2020

    work page 2020

  23. [23]

    Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation

    Chun-Hung Liu and Irene Muzi. Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation. Journal of Combinatorial Theory, Series B , 158:210--251, 2023

    work page 2023

  24. [24]

    Well-quasi-orders on embedded planar graphs

    Corentin Lunel and Cl \'e ment Maria. Well-quasi-orders on embedded planar graphs. arXiv preprint arXiv:2512.04074 , 2025

    work page arXiv 2025

  25. [25]

    Local structure for vertex-minors

    Rose McCarty. Local structure for vertex-minors . PhD thesis, University of Waterloo, 2021

    work page 2021

  26. [26]

    Well-quasi-order of plane minors and an application to link diagrams

    Carolina Medina, Bojan Mohar, and Gelasio Salazar. Well-quasi-order of plane minors and an application to link diagrams. arXiv preprint arXiv:1905.01830 , 2019

    work page arXiv 1905

  27. [27]

    Paths and topological minors in directed and undirected graphs

    Irene Muzi. Paths and topological minors in directed and undirected graphs . PhD thesis, Ph. D. Dissertation, Sapienza Universita Di Roma, 2017

    work page 2017

  28. [28]

    On well-quasi-ordering finite trees

    C St JA Nash-Williams. On well-quasi-ordering finite trees. In Mathematical Proceedings of the Cambridge Philosophical Society , volume 59, pages 833--835. Cambridge University Press, 1963

    work page 1963

  29. [29]

    Rank-width and well-quasi-ordering

    Sang-il Oum. Rank-width and well-quasi-ordering. SIAM Journal on Discrete Mathematics , 22(2):666--682, 2008

    work page 2008

  30. [30]

    Graph minors

    Neil Robertson and Paul D Seymour. Graph minors. iv. tree-width and well-quasi-ordering. Journal of Combinatorial Theory, Series B , 48(2):227--254, 1990

    work page 1990

  31. [31]

    Robertson and P.D

    N. Robertson and P.D. Seymour. Graph Minors . XIII . The Disjoint Paths Problem . Journal of Combinatorial Theory, Series B , 63(1):65--110, January 1995. https://doi.org/10.1006/jctb.1995.1006 doi:10.1006/jctb.1995.1006

    work page doi:10.1006/jctb.1995.1006 1995

  32. [32]

    Graph minors

    Neil Robertson and Paul D Seymour. Graph minors. xix. well-quasi-ordering on a surface. Journal of Combinatorial Theory, Series B , 90(2):325--385, 2004

    work page 2004

  33. [33]

    Graph minors

    Neil Robertson and Paul D Seymour. Graph minors. xx. wagner's conjecture. Journal of Combinatorial Theory, Series B , 92(2):325--357, 2004

    work page 2004

  34. [34]

    Graph minors xxiii

    Neil Robertson and Paul D Seymour. Graph minors xxiii. nash-williams' immersion conjecture. J. Comb. Theory, Ser. B , 100(2):181--205, 2010

    work page 2010

  35. [35]

    Seymour and Robin Thomas

    Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. Combinatorica , 14(2):217--241, 1994

    work page 1994