Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?

Question

Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: each turn, the first player choses either to add a vertex from $V_1$ to $A_1$ or a vertex from $V_2$ to $A_2$. Then the second player also choses either to add a vertex from $V_1$ to $A_1$ or a vertex from $V_2$ to $A_2$. After it, if the subgraphs induced by $A_1$ and $A_2$ are not isomorphic, the game terminates. Otherwise, it continue and the next turn begins. If the game has terminated on the $n$-th turn, then the revenue of the first player is $\frac{1}{n}$ and the revenue of the second player is $n$. If the game lasts indefinitely, then the revenue of the first player is $0$ and the revenue of the second player is infinite.

Let’s define $d(\Gamma_1, \Gamma_2)$ as the revenue of the first player, provided that both players use best strategies possible. Is it true, that $d$ is a metric on the set of all isomorphism classes of graphs with countable number of vertices?

The proof that $d(\Gamma_1, \Gamma_2) = 0$ iff $\Gamma_1 \cong \Gamma_2$ can be found here.

However, I do not know, whether the triangle inequality $d(\Gamma_1, \Gamma_3) \leq d(\Gamma_1, \Gamma_2) + d(\Gamma_1, \Gamma_3)$ holds here.

I have already asked this question a while ago here, but it remained unnoticed.

Answer 1

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3)$ game, then he can survive for $\min(n,m)$ steps in the $(\Gamma_1,\Gamma_3)$ game.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the larger of the distances from $\Gamma_1$ to $\Gamma_2$ or from $\Gamma_2$ to $\Gamma_3$, respectively and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

But actually, I think you should probably use the Ehrenfeucht–Fraïssé style games, where the isomorphism must be that arising from the play, instead of what you wrote. For example, your claim that $D(\Gamma_1,\Gamma_2)=0$ if and only if $\Gamma_1\cong\Gamma_2$ is not correct in general, unless you use the Ehrenfeucht–Fraïssé style winning conditions. To see this, observe that any two infinite linear orders (coded as graphs) will have distance 0 according to your rules, since any two linear orders of length $n$ are isomorphic, but they need not be Ehrenfeucht–Fraïssé equivalent.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.