Alladi Ramakrishnan Hall

Definability and decidability in the first order theory of graph order

Ramanathan S Thinniyam

IMSc, HBNI

(This is the public defense for Ramanathan's PhD thesis.)

Consider the set G of isomorphism types of finite, simple, undirected
graphs. The induced subgraph, subgraph and minor relations form partial
orders over G, which we call graph orders. We study the first order theory
of such graphs orders, with an emphasis on definability and decidability.

With regards to definability, we show that graph orders are as powerful as
arithmetic (more technically, have the maximal definability property for
arithmetical structures). This implies the undecidability of the full first
order theory of each graph order, motivating the search for decidable
fragments. We concentrate on syntactic fragments of the induced subgraph
order. The main problem left open is the decidability of the two variable
fragment of the induced subgraph order expanded by constants. A positive
resolution of this problem would generalise the result already known for
the subword order, while a negative resolution would be very surprising.