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.
Done