Connecticut CT Logic Seminar

The logic of graph decompositions

Stephen Flood (University of Connecticut)

Monday, February 24, 2014 4:45 pm
MSB 203

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.