pith. sign in

arxiv: 2405.15249 · v3 · pith:AOVEYIEVnew · submitted 2024-05-24 · 🧮 math.CO

Connectoids II: existence of normal trees

Nathan Bowler , Florian Reich This is my paper

Pith reviewed 2026-05-24 00:44 UTC · model grok-4.3

classification 🧮 math.CO
keywords connectoidsnormal spanning treesdispersed setsend spacecountable separation numberJung characterisationinfinite graphsmatroids
0
0 comments X

The pith

A connectoid has a normal spanning tree precisely when its ground set admits a well-ordering of countable separation number.

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

The paper establishes that normal spanning trees exist in a connectoid exactly when the ground set can be well-ordered so every cut has countable separation number. This extends Jung's dispersed-set characterisation from undirected graphs to the broader class of connectoids, which encode connectivity in directed graphs, hypergraphs and finitary matroids. The authors also prove that global existence follows once normal trees exist in a neighbourhood of each end. Readers gain a single criterion that replaces separate arguments for each type of structure.

Core claim

We show that a connectoid has a normal spanning tree if and only if its groundset can be well-ordered in a certain way, called countable separation number. We extend Jung's famous characterisation via dispersed sets to connectoids, and prove that normal spanning trees exist if they exist in some neighbourhood of each end. Furthermore, we show that a connectoid has a normal spanning tree if and only if its groundset can be well-ordered in a certain way, called countable separation number.

What carries the argument

The countable-separation-number well-ordering of the ground set, which replaces the classical dispersed-set condition while using the universal end space developed for connectoids.

If this is right

  • Normal spanning trees exist globally precisely when they exist locally near each end.
  • The dispersed-set condition of Jung carries over verbatim once the connectoid end space is in place.
  • Existence of normal trees is equivalent to the ground set having countable separation number.
  • The same criterion decides normal trees for hypergraphs, directed graphs and finitary matroids alike.

Where Pith is reading between the lines

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

  • The criterion immediately supplies normal-tree arguments for any finitary matroid whose ground set satisfies the ordering condition.
  • One can now ask whether every connectoid of countable separation number also admits a normal tree that respects a given orientation or hyperedge structure.
  • The result suggests checking whether other classical infinite-graph theorems, such as those on rayless graphs, extend verbatim once the connectoid axioms are verified.

Load-bearing premise

The dispersed sets and end neighbourhoods defined for connectoids behave enough like the corresponding objects in undirected graphs for Jung's characterisation to transfer directly.

What would settle it

A concrete connectoid whose ground set admits a countable-separation well-ordering yet possesses no normal spanning tree, or one in which every end neighbourhood has a normal tree but the whole object does not.

Figures

Figures reproduced from arXiv: 2405.15249 by Florian Reich, Nathan Bowler.

Figure 1
Figure 1. Figure 1: The schema of the directed graph D in Proposition 10.1 for some i < ω and j < ω1. Proposition 10.1 suggests that we should weaken the definition of minor if we want to find a characterisation via countable colouring number. But we do not want to weaken the notion of minor too much: We still want the property of having a normal spanning tree to be preserved under taking minors The following type of minor se… view at source ↗
read the original abstract

In this series, we introduce and investigate the concept of connectoids, which captures the connectivity structure of various discrete objects such as undirected graphs, directed graphs, bidirected graphs, hypergraphs and finitary matroids. In the first paper, we developed a universal end space theory based on connectoids that unifies the existing end spaces of undirected and directed graphs. In this paper, we establish normal trees of connectoids as a natural generalisation of normal trees of undirected graphs, which are one of the most important tools in infinite graph theory. More precisely, we show that the existence of normal trees of connectoids can be characterised in the same way as for normal trees of undirected graphs: We extend Jung's famous characterisation via dispersed sets to connectoids, and prove that normal spanning trees exist if they exist in some neighbourhood of each end. Furthermore, we show that a connectoid has a normal spanning tree if and only if its groundset can be well-ordered in a certain way, called countable separation number.

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 / 2 minor

Summary. The paper claims that a connectoid admits a normal spanning tree precisely when its ground set admits a well-ordering of countable separation number; this is obtained by lifting Jung's dispersed-set characterization to the connectoid setting via the end-space notions of Part I, together with the auxiliary statement that normal spanning trees exist globally if and only if they exist in a neighbourhood of every end.

Significance. If the claimed equivalences hold, the work supplies a uniform, if-and-only-if characterisation of normal spanning trees that applies simultaneously to undirected graphs, directed graphs, bidirected graphs, hypergraphs and finitary matroids. The explicit reduction to a well-ordering condition on the ground set is a concrete, falsifiable strengthening of the classical Jung theorem and therefore constitutes a genuine advance in the structural theory of infinite connectivity.

minor comments (2)
  1. The dependence on the end-space definitions, dispersed-set notion and neighbourhood-of-an-end construction from Part I is stated but not recapitulated; a short self-contained paragraph summarising the relevant notions would improve readability for readers who have not yet consulted the preceding paper.
  2. The abstract asserts that 'proofs exist' for the two main extensions of Jung's theorem; the introduction or §2 should contain an explicit roadmap indicating which lemmas from Part I are invoked and where the new arguments begin.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough reading and positive recommendation to accept the manuscript. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper establishes an if-and-only-if characterisation of normal spanning trees for connectoids by extending Jung's theorem on dispersed sets, using end-space definitions from the prior paper in the series only as foundational input. The new equivalences to well-orderings with countable separation number and neighbourhood conditions are proved directly in this work via explicit constructions and arguments that do not reduce to re-expressing prior fitted quantities or self-referential definitions. No load-bearing step collapses by construction to an input or unverified self-citation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims depend on the connectoid axioms and end-space construction introduced in part I of the series together with standard set-theoretic principles for well-orderings; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Axioms of ZFC set theory, including the axiom of choice, sufficient to guarantee well-orderings of the ground set
    Invoked to state the countable separation number condition on the ground set.

pith-pipeline@v0.9.0 · 5694 in / 1219 out tokens · 24692 ms · 2026-05-24T00:44:34.465492+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

13 extracted references · 13 canonical work pages

  1. [1]

    N.Bowler,J.Carmesin,P.Komjáth,andC.Reiher, The colouring number of infinite graphs,Combinatorica 39 (2019), 1225–1235

    work page 2019

  2. [2]

    Bowler and F

    N. Bowler and F. Reich,Connectoids I: a universal end space theory, arXiv preprint arXiv:2405.14704 (2024)

    work page arXiv 2024

  3. [3]

    Diestel,Normal tree orders for infinite graphs, Transactions of the American Mathematical Society 345 (1994), no

    J-M Brochet and R. Diestel,Normal tree orders for infinite graphs, Transactions of the American Mathematical Society 345 (1994), no. 2, 871–895

    work page 1994

  4. [4]

    Diestel,Graph Theory, 5th ed., Springer-Verlag, 2017

    R. Diestel,Graph Theory, 5th ed., Springer-Verlag, 2017

    work page 2017

  5. [5]

    Diestel and I

    R. Diestel and I. Leader,Normal spanning trees, Aronszajn trees and excluded minors, Journal of the London Mathematical Society63 (2001), no. 1, 16–32

    work page 2001

  6. [6]

    Fodor,Eine Bemerkung zur Theorie der regressiven Funktionen, Acta Sci

    G. Fodor,Eine Bemerkung zur Theorie der regressiven Funktionen, Acta Sci. Math.(Szeged)17 (1956), 139–142

    work page 1956

  7. [7]

    Heuer,Excluding a full grid minor, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 87 (2017), no

    K. Heuer,Excluding a full grid minor, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 87 (2017), no. 2, 265–274

    work page 2017

  8. [8]

    Johnson, N

    T. Johnson, N. Robertson, P. D Seymour, and R. Thomas,Directed tree-width, Journal of Combinatorial Theory, Series B82 (2001), no. 1, 138–154

    work page 2001

  9. [9]

    A Jung,Wurzelbäume und unendliche Wege in Graphen, Mathematische Nachrichten 41 (1969), no

    H. A Jung,Wurzelbäume und unendliche Wege in Graphen, Mathematische Nachrichten 41 (1969), no. 1-3, 1–22

    work page 1969

  10. [10]

    König,Über eine Schlussweise aus dem Endlichen ins Unendliche, Acta Sci

    D. König,Über eine Schlussweise aus dem Endlichen ins Unendliche, Acta Sci. Math.(Szeged)3 (1927), no. 2-3, 121–130. 1In undirected graphs, every graph-theoretic minor is a weak minor but weak minors are in general not graph-theoretic minors. CONNECTOIDS II: EXISTENCE OF NORMAL TREES 33

    work page 1927

  11. [11]

    Kurkofka, R

    J. Kurkofka, R. Melcher, and M. Pitz,Approximating infinite graphs by normal trees, Journal of Combi- natorial Theory, Series B148 (2021), 173–183

    work page 2021

  12. [12]

    Pitz,Proof of Halin’s normal spanning tree conjecture, Israel Journal of Mathematics246 (2021), no

    M. Pitz,Proof of Halin’s normal spanning tree conjecture, Israel Journal of Mathematics246 (2021), no. 1, 353–370

    work page 2021

  13. [13]

    Universität Hamburg, Department of Mathematics, Bundesstrasse 55 (Geomatikum), 20146 Hamburg, Germany Email address: {nathan.bowler, florian.reich}@uni-hamburg.de

    , Quickly proving Diestel’s normal spanning tree criterion, The Electronic Journal of Combinatorics (2021), P3–59. Universität Hamburg, Department of Mathematics, Bundesstrasse 55 (Geomatikum), 20146 Hamburg, Germany Email address: {nathan.bowler, florian.reich}@uni-hamburg.de

    work page 2021