Tag Archives: graph

Graph isomorphism

Fix an $\omega$ -categorical structure $\atoms$ . The simplest, and already interesting case is $(\mathbb N,=)$ , the pure countable set.

We consider the definable graph isomorphism problem for graphs which are definable (equivalently, interpret in) $\atoms$ :

Problem: DefGraphIso

Input: Two definable graphs $G,H$

Output: Yes, if $G$ and $H$ are isomorphic, No otherwise.

Below we make some very basic observations concerning this problem.