White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Proof Theory of Graph Minors and Tree Embeddings

Krombholz, Martin Rudolf Arne (2018) Proof Theory of Graph Minors and Tree Embeddings. PhD thesis, University of Leeds.

[img]
Preview
Text
thesis.pdf - Final eThesis - complete (pdf)
Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (876Kb) | Preview

Abstract

This thesis explores metamathematical properties of theorems appearing in the Graph Minors series. A number of these theorems have been known to have very high proof-theoretic strength, but an upper bound on many of them, including the graph minor theorem, had never been proved. We give such upper bounds, by showing that any proofs in the Graph Minors series can be carried out within a system of Pi^1_1-comprehension augmented with induction and bar-induction principles for certain classes of formulas. This establishes a narrow corridor for the possible proof-theoretic strength of many strong combinatorial principles, including the graph minor theorem, immersion theorem, theorems about patchwork containment, and various restrictions, extensions and labelled versions of these theorems. We also determine the precise proof-theoretic strength of some restrictions of the graph minor theorem, and show that they are equivalent to other restricted versions that had been considered before. Finally, we present a combinatorial theorem employing ordinal labelled trees ordered by embedding with gap-condition that may additionally have well-quasi-ordered labels on the vertices, which turns out not to be provable in the theory Pi^1_1-CA. This result suggests a potential for raising the lower bounds of the immersion theorem, and the thesis concludes by outlining this possibility and other avenues for further research.

Item Type: Thesis (PhD)
Keywords: Graph Minor Theorem, Proof Theory
Academic Units: The University of Leeds > Faculty of Maths and Physical Sciences (Leeds) > School of Mathematics (Leeds) > Pure Mathematics (Leeds)
Depositing User: Martin Krombholz
Date Deposited: 23 Jul 2018 10:28
Last Modified: 23 Jul 2018 10:28
URI: http://etheses.whiterose.ac.uk/id/eprint/20834

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)