Connecticut CT Logic Seminar
The logic of graph decompositions
Stephen Flood (University of Connecticut)
Monday, February 24, 2014
The theory of simplicial graph decompositions studies the infinite graphs that can be built using a sequence of irreducible graphs which are pasted together at complete subgraphs. We study the strength of several ``existence theorems'', which say that certain graphs admit such a decomposition.
We will discuss the strength of one such existence theorem, known as Halin's Theorem, from the perspective of reverse mathematics and computability theory. In addition, we will give upper and lower bounds on the possible ordinal lengths of general prime decompositions.