¿Un juego de "imitación" en gráficos infinitos?

Question

Supongamos que $\Gamma_1(V_1, E_1)$ y $\Gamma_2(V_2, E_2)$ son grafos simples con un número contable de vértices. Y supongamos $A_1$ y $A_2$ están inicialmente vacíos. Supongamos que dos jugadores juegan el siguiente juego: en cada turno, el primer jugador elige añadir un vértice de $V_1$ a $A_1$ o un vértice de $V_2$ a $A_2$ . A continuación, el segundo jugador también elige añadir un vértice de $V_1$ a $A_1$ o un vértice de $V_2$ a $A_2$ . Después, si los subgráficos inducidos por $A_1$ y $A_2$ no son isomórficos, el primer jugador gana. En caso contrario, el juego continúa. El segundo jugador gana, si es capaz de mantener el juego indefinidamente.

¿Es cierto que el segundo jugador tiene una estrategia ganadora si $\Gamma_1 \cong \Gamma_2$ ?

Sé que si $\Gamma_1 \cong \Gamma_2$ entonces el segundo jugador puede prolongar la partida indefinidamente simplemente copiando los movimientos del primer jugador en el gráfico diferente. Pero, ¿qué pasa con lo contrario? ¿Es cierto?

Answer 1

En primer lugar, puede asumir que $A_1$ y $A_2$ tienen el mismo número de vértices después de cada par de movimientos (si no, el jugador 2 está regalando el juego).

Lema : Si cada vértice $v_i\in\Gamma_1$ finalmente se envía a $A_1$ y cada vértice $w_i\in\Gamma_2$ se envía a $A_2$ entonces existe un isomorfismo entre $\Gamma_1$ y $\Gamma_2$ .

Después de la $i$ par de movimientos, un vértice $v_i\in\Gamma_1$ se enviará a $A_1$ y $w_i\in\Gamma_2$ se enviará a $A_2$ . El mapeo que envía todos los $v_i$ a su correspondiente $w_i$ es un isomorfismo. Cualquier par de vértices $v_j,v_k\in \Gamma_1$ ambos terminarán en $A_1$ después de un cierto número de movimientos, y son adyacentes si los correspondientes $w_j,w_k$ son adyacentes.

Ahora podemos construir una estrategia ganadora para el jugador 1 cuando los dos gráficos no son isomórficos. El jugador 1 ordena todos los vértices de ambos grafos como $v_1,w_1,v_2,w_2,v_3,w_3...$ .

En cada turno el jugador 1 elige el siguiente vértice de su ordenación que no esté ya en $A_1$ o $A_2$ . Dado que cada vértice de $\Gamma_1$ y $\Gamma_2$ finalmente se elige, o bien la obra termina o los dos grafos son isomorfos.