0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Maybe even $d(\Gamma_1,\Gamma_3)\le\max\{d(\Gamma_1,\Gamma_2),d(\Gamma_2,\Gamma_3)\}$? $\endgroup$ – bof Nov 18 '19 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.