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.

The input is represented by two expressions defining G and H, such as the one below, defining the infinite Johnson graph:

    \begin{align*}V&=\set{\set{a,b}:a,b\in\atoms,a\neq b}\\ E&=\set{\set{\set{a,b},\set{b,c}}:a,b,c\in\atoms,a\neq b\land b\neq c\land a\neq c}\\G&=(V,E) \end{align*}

(in general, an expression is a nested application of finite unions of set-builder expressions with parameters ranging over \atoms using first-order guard formulas in the language of \atoms).

Remark 1. Equivalently, G and H are specified by two first-order interpretations from \atoms, where an interpretation specifies the dimension d\in\mathbb N, a formula \phi_\text{dom} with d free variables, a formula \phi_{\sim} with 2d free variables, and a formula \phi_{E} with 2d free variables, and defines the graph (D,E)/{\sim} where: D\subset \atoms^d is the interpretation of \phi_\text{dom} in \atoms, E\subset\atoms^{2d} is the interpretation of \phi_E in \atoms, which assumed to be contained in D\times D\subset \atoms^{2d}, and {\sim}\subset\atoms^{2d} is the interpretation of \phi_{\sim} in \atoms, and is assumed to be a congruence of the graph (D,E) (otherwise, the graph G is undefined).

Remark 2. We assume that the expressions do not contain constants from \atoms. This assumption can be dropped without generality if \atoms=(\mathbb N,=), since in that case, every definable structure \str A whose definition uses constants can be effectively converted into isomorphic structures defined by expressions which do not use constants. I don’t know whether this works for other \atoms.

Example 1. Since definable graphs are closed under disjoint unions, the disjoint union H of two copies of the Johnson graph G is also definable. Clearly G embeds into H. It is not difficult to see that also H embeds into G: it is enough to partition all atoms into two disjoint, infinite sets A,B, and then consider the subgraphs of G induces by those vertices, which only use atoms from the set A (respectively, B). Clearly, both are isomorphic to G. However,  the graph G is not isomorphic to H, as G is connected, and of diameter 3 (there is a path from the vertex \set{a,b} to the vertex \set{c,d}, which goes through the vertex \set{b,c},\set{c,d}). Therefore, the graphs G and H can be distinguished by the first-order sentence \forall v\forall w\exists u. E(v,u)\land E(u,w).

We will use the following, standard result.

Lemma 1. Suppose that \str A is definable over an \omega-categorical structure \atoms. Then

  1. \str A is \omega-categorical,
  2. Every relation R\subset \str A^k which is invariant under the automorphisms of \str A is also invariant under the automorphisms of \atoms (the converse implication does not always hold),
  3.  A relation R\subset \str A^k is \aut{\str A}-invariant if and only if it is first-order definable in \str A, i.e., it can be defined in the structure \str A.

Below are several simple observations concerning the above decision problem.

Proposition 1. The problem DefIso is co-recursively enumerable.

Proof. Since G is \omega-categorical, H is isomorphic to G if and only it satisfies exactly the same first-order sentences as G. For a given sentence \phi, one can effectively test whether it holds in G, or in H. One can enumerate all sentences \phi, and for each of them test whether it holds in G and not in H. Such a formula is found if and only if G and H are non-isomorphic.\square

We now list several other related problems. Unless stated otherwise, when we say definable we mean definable with respect to \atoms, without constants.

  1. DefStructureIso. The input consists of two definable relational structures \str A=(A,R_1^{\str A},R_2^{\str A},\ldots,R_k^{\str A}) and \str B=(B,R_1^{\str B},R_2^{\str B},\ldots,R_k^{\str B}), and the question is whether they are isomorphic.
  2. DefRel. The input consists of a definable relational structure \str A and a definable relation R\subset \str A^k, and the question is whether R is first-order definable in \str A. This problem is basically Problem 29 stated in  the paper “Decidability of Definability” by Bodirsky, Pinsker, Tsankov. There, they consider the case when \atoms is an ordered, homogeneous, Ramsey, finitely bounded relational structure over a finite signature (this implies \omega-categoricity, in particular), and \str A is a reduct of \atoms (i.e., it is definable over \atoms and has the same domain as \atoms).
  3. DefUnaryRel. The same question as above, but restricted to unary relations U\subset \str A.
  4. Orbit. The input consists of a definable structure \str A and a definable unary relation U\subset \str A, and the question is whether U is a single orbit with respect to \aut{\str A}, the automorphism group of \str A.
  5. SameOrbit. The input consists of a definable relational structure \str A and two elements x,y\in \str A. The question is whether x and y lie in the same orbit under the group of automorphisms of \str A. The elements x and y are represented by specifying their orbits X and Y under the action of \aut \atoms. It follows from Lemma 1, item 2, that the answer to the question does not depend on the choice of the representatives x\in X,y\in Y. (One could also represent the elements x,y using expressions with constants from \atoms; however, in the proof below we will avoid introducing extra constants).

Proposition 2. All the above problems, and the DefIso problem, are inter-reducible.

Proof. The DefGraphIso is a special case of the DefStructureIso problem, and conversely, for any finite relational signature \Sigma it is standard to construct a first-order transduction T converting \Sigma-structures into graphs, so that \str A and \str B are isomorphic if and only if T(\str A) and T(\str B) are isomorphic. The structures T(\str A) and T(\str B) are computable from \str A and \str B.

The DefStructureIso problem reduces to the SameOrbit problem. Given a structure \str A, construct a structure \str A' obtained from \str A by adjoining a new ‘apex’ node a, connected to all nodes of \str A by a new relation called E. Given two structures \str A and \str B, construct the disjoint union \str A'\sqcup \str B'. Then \str A and \str B are isomorphic if and only if the two apices are in the same orbit of \str A'\sqcup \str B'.

Conversely, the SameOrbit problem reduces to the DefStructureIso problem: Given \str A,X,Y, where X and Y are \aut \atoms-orbits of \str A, the sets X and Y are contained in a single \aut{\str A}-orbit if and only if the structure (\str A,X) is isomorphic to the structure (\str A, Y).

The SameOrbit problem reduces to the Orbit problem. Indeed, assuming the Orbit problem is decidable, one can enumerate all \aut{\str A}-orbits of a given structure \str A: by the second item of Lemma 1, it suffices to enumerate all unions of \aut\atoms-orbits of \str A, and for each such union, test whether it is an orbit of \str A under \aut{\str A}.

Conversely, the Orbit problem reduces to the SameOrbit problem: one can enumerate all pairs X,Y of \aut\atoms-orbits contained in U, and for each of them test whether they are contained in the same \aut{\str A}-orbit of \str A.

The Orbit problem reduces to the DefUnaryRel problem: U\subset \str A is an \aut{\str A}-orbit if and only if it is an inclusion-minimal \aut{\str A}-invariant subset of \str A. All such invariant subsets can be enumerated, since they are unions of \aut \atoms-invariant subsets of \str A by the second item of Lemma 1, and a union of \aut \atoms-orbits of \str A is \aut{\str A}-invariant if and only if it is definable in \str A. Minimality can be checked, since containment of two definable sets is decidable.

Conversely, the DefUnaryRel problem reduces to the Orbit problem, since by the third item of Lemma 1, a unary relation U\subset \str A is definable if and only if it is a union of \aut{\str A}-orbits of \str A.

Clearly, the DefUnaryRel problem is a special case of the DefRel problem. Conversely, given a structure \str A and a relation R\subset \str A^k, we expand the structure \str A to the structure (\str A\sqcup\str A^k,R,\pi_1,\ldots,\pi_k), where R\subset \str A^k is treated as a unary relation on \str A\sqcup\str A^k, and \pi_i is treated as a binary relation– the graph of the ith projection from \str A^k to \str A.\square

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>