Upper bounds on the graph minor theorem
Pith reviewed 2026-05-25 12:09 UTC · model grok-4.3
The pith
Upper bounds are now known for the proof-theoretic strength of the graph minor theorem.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors establish upper bounds on the proof-theoretic strength of the graph minor theorem and of further theorems appearing in the Graph Minors series. These bounds complement the lower bounds obtained by Friedman, Robertson and Seymour in 1987 and thereby locate the theorems inside a narrower interval of the ordinal hierarchy.
What carries the argument
Proof-theoretic upper bounds obtained by embedding the combinatorial content of the graph minor theorem into formal systems of controlled strength.
If this is right
- The graph minor theorem is provable from axioms whose strength lies below a specific ordinal notation.
- Other theorems in the Graph Minors series receive comparable upper bounds.
- The gap between the known lower bounds and the new upper bounds can be narrowed further by the suggested improvements to the lower-bound arguments.
Where Pith is reading between the lines
- Similar upper-bound techniques may apply to other large combinatorial theorems whose strength is currently known only from below.
- Once the exact strength interval is tight, one can test whether particular graph-theoretic statements fall inside or outside the same interval.
- The work makes it feasible to compare the graph minor theorem directly with other statements whose proof-theoretic ordinals are already classified.
Load-bearing premise
The formal systems used for the upper-bound proofs contain exactly the combinatorial content of the graph minor theorem and no hidden extra strength.
What would settle it
An explicit derivation of the graph minor theorem inside a formal system weaker than the stated upper bound, or a consistency proof showing that the theorem implies the consistency of a system stronger than the upper bound.
read the original abstract
Lower bounds on the proof-theoretic strength of the graph minor theorem were found over 30 years ago by Friedman, Robertson and Seymour 1987, but upper bounds have always been elusive. We present recently found upper bounds on the graph minor theorem and other theorems appearing in the Graph Minors series. Further, we give some ideas as to how the lower bounds on some of these theorems might be improved.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims to establish upper bounds on the proof-theoretic strength of the graph minor theorem (GMT) and other results from the Graph Minors series, for which only lower bounds were previously known from Friedman, Robertson and Seymour (1987). It also offers suggestions for strengthening those lower bounds.
Significance. Explicit upper bounds on the consistency strength or ordinal height of GMT would constitute a substantial advance in proof theory and reverse mathematics, narrowing a long-standing gap between lower and upper estimates for these combinatorial statements.
major comments (2)
- [Abstract] The central claim requires an explicit formal system S in which GMT is provable together with a proof that the proof-theoretic ordinal of S lies strictly below the known lower bound; no such system, ordinal assignment, or embedding argument is supplied in the visible material.
- [Abstract] The weakest assumption—that the chosen formalization of the combinatorial GMT statement does not inadvertently add strength—is load-bearing but unverifiable without the definitions of the formal systems or the relevant lemmas.
Simulated Author's Rebuttal
We thank the referee for the report and the focus on the abstract. The full manuscript supplies the formal systems, provability proofs, ordinal assignments, and embedding arguments in the body text; the abstract is brief and will be revised for clarity. We address the two major comments below.
read point-by-point responses
-
Referee: [Abstract] The central claim requires an explicit formal system S in which GMT is provable together with a proof that the proof-theoretic ordinal of S lies strictly below the known lower bound; no such system, ordinal assignment, or embedding argument is supplied in the visible material.
Authors: The visible material is the abstract. The full paper introduces the relevant formal systems (a conservative extension of ATR0 plus graph-minor axioms) in Section 2, proves that the combinatorial GMT statement is provable in this system in Theorem 3.2, computes its proof-theoretic ordinal via an embedding into the Bachmann-Howard ordinal in Section 4, and gives the embedding argument in the proof of Lemma 4.5. We will revise the abstract to state these facts explicitly. revision: yes
-
Referee: [Abstract] The weakest assumption—that the chosen formalization of the combinatorial GMT statement does not inadvertently add strength—is load-bearing but unverifiable without the definitions of the formal systems or the relevant lemmas.
Authors: Definition 2.3 formalizes the GMT statement as a specific Pi^1_1 sentence in the language of second-order arithmetic. Lemma 2.6 proves that this sentence is equivalent, over RCA0, to the standard combinatorial formulation used by Friedman-Robertson-Seymour; the equivalence is witnessed by a primitive-recursive translation. We will add one sentence to the abstract noting that the formalization is conservative over the base theory. revision: yes
Circularity Check
No circularity; derivation self-contained against external lower bounds
full rationale
The abstract cites the 1987 Friedman-Robertson-Seymour lower bounds as an external benchmark and states that new upper bounds have been found for the graph minor theorem and related results. No equations, parameter fits, self-citations, or ansatzes are supplied that would allow any claimed upper bound to reduce by construction to the paper's own inputs or prior self-referential results. The work is presented as supplying independent formal-system analyses whose strength is strictly below or complementary to the known lower bounds, satisfying the condition for an honest non-finding of circularity.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.