Interval graphs and reverse mathematics

Marta Fiori Carones, University of Udine. Part of the PCC Seminar Series.

This talk deals with the characterisation of interval graphs from the point of view of reverse mathematics, in particular we try to understand which axioms are needed in the context of subsystems of second order arithmetic to prove various characterisations of these graphs. Furthermore, we attempt to analyse the interplay between interval orders and interval graphs. Alberto Marcone (2007) already settled the former question for interval orders and this paper follows his path. An interval graph is a graph whose vertices can be mapped in intervals of a linear order such that if two vertices are related, then the intervals associated to them overlap. Different notions of intervals give raise to different notions of interval graphs (and orders), which  collapse to one in WKL0. On this respect, interval graphs show the same behaviour of interval orders. On the other hand, interval graphs and interval orders have different strength with respect to their characterisations in terms of structural properties. While RCA0 suffices to prove the combinatorial characterisation of interval orders, WKL0 is required for interval graphs. Moreover, given an interval graph it is possible to define an associated interval order and vice versa. Even in this respect, the different definitions of interval graphs and orders mentioned before play a role in analysing the strength of these theorems.