Logic Seminar, Stephen Flood (UConn): 'Separating Decomposability and Tree- Decomposability'

Monday, March 23, 2015
4:45 PM - 6:00 PM (ET)
ESC 638
Event Type
Lecture
Contact
Philip Scowcroft, x2172
Department
Academic
Link
https://eaglet.wesleyan.edu/MasterCalendar/EventDetails.aspx?EventDetailId=48508

Abstract: The theory of graph decompositions studies the infinite graphs that can be built using a sequence of irreducible graphs which are pasted together at complete subgraphs. In this theory, there are several combinatorial characterizations of the tree-decomposable graphs, but a combinatorial characterization of general decomposable graphs has proved elusive.In this talk, we approach this question from the perspective of mathematical logic. We show that there is indeed a difference between characterizing decomposable and tree-decomposable graphs. More precisely, we show that the index set of computable decomposable graphs is $\Pi^1_1$ hard and $\Sigma^1_2$ definable, whereas the index set of computable tree-decomposable graphs is $\Sigma^1_1$ definable.

Get Directions
Event Date
Event Time
Title
Building