Back to Calendar

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.