10.23638/LMCS-14(3:21)2018
Thinniyam, Ramanathan S.
Ramanathan S.
Thinniyam
Defining Recursive Predicates in Graph Orders
episciences.org
2018
Computer Science - Logic in Computer Science
contact@episciences.org
episciences.org
2017-09-12T07:29:27+02:00
2018-09-24T09:05:41+02:00
2018-09-24
eng
Journal article
https://lmcs.episciences.org/3923
arXiv:1709.03060
1860-5974
PDF
1
Logical Methods in Computer Science ; Volume 14, Issue 3 ; 1860-5974
We study the first order theory of structures over graphs i.e. structures of
the form ($\mathcal{G},\tau$) where $\mathcal{G}$ is the set of all
(isomorphism types of) finite undirected graphs and $\tau$ some vocabulary. We
define the notion of a recursive predicate over graphs using Turing Machine
recognizable string encodings of graphs. We also define the notion of an
arithmetical relation over graphs using a total order $\leq_t$ on the set
$\mathcal{G}$ such that ($\mathcal{G},\leq_t$) is isomorphic to
($\mathbb{N},\leq$).
We introduce the notion of a \textit{capable} structure over graphs, which is
one satisfying the conditions : (1) definability of arithmetic, (2)
definability of cardinality of a graph, and (3) definability of two particular
graph predicates related to vertex labellings of graphs. We then show any
capable structure can define every arithmetical predicate over graphs. As a
corollary, any capable structure also defines every recursive graph relation.
We identify capable structures which are expansions of graph orders, which are
structures of the form ($\mathcal{G},\leq$) where $\leq$ is a partial order. We
show that the subgraph order i.e. ($\mathcal{G},\leq_s$), induced subgraph
order with one constant $P_3$ i.e. ($\mathcal{G},\leq_i,P_3$) and an expansion
of the minor order for counting edges i.e. ($\mathcal{G},\leq_m,sameSize(x,y)$)
are capable structures. In the course of the proof, we show the definability of
several natural graph theoretic predicates in the subgraph order which may be
of independent interest. We discuss the implications of our results and
connections to Descriptive Complexity.