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

Done