The strength of some restricted forms of the graph minor theorem

Martin Krombholz, University of Leeds. Part of the logic seminar series.

In 1985 Simpson presented a combinatorial result due to Friedman that had higher proof theoretic strength than the systems usually considered in reverse mathematics. His construction involved trees labelled with natural numbers ordered by embedding with a so-called gap condition. Later, Friedman, Robertson and Seymour showed that these labelled trees could be simulated by graphs of bounded size which are glued together in a tree-like shape and ordered under the minor relation. They also claimed that this construction could be done using only graphs embeddable into the plane. In this talk I will sketch the above mentioned results and give a proof of the claim. I will then discuss how this impacts the graph minor theorem restricted to graphs embeddable into a fixed surface. Finally I will give some thoughts about what this means for settling the strength of the full graph minor theorem.

Martin Krombholz, University of Leeds