Alladi Ramakrishnan Hall

Definability in First order theories of graph orderings

Ramanathan S Thinniyam

IMSc

We study definability in the first order theory of graph order: that is, the set of
all simple finite graphs ordered by either the minor, subgraph or induced subgraph relation.
We show that natural graph families like cycles and trees are definable, as also
notions like connectivity, maximum degree etc. This naturally comes with a price:
bi-interpretability with arithmetic. We discuss implications for formalizing
statements of graph theory in such theories of order.

This work (co-authored with R Ramanujam), will be presented at LFCS 2016.