Reconstrucción a partir de la gráfica de fichas.

Question

Sea $G$ una gráfica. La gráfica de fichas $F_k(G)$ de $G$, es la gráfica cuyos vértices

son todos los subconjuntos de $k$ vértices de $G$, dos de ellos adyacentes si su  diferencia

simétrica es un par de vértices adyacentes en $G$. La idea es que formamos una nueva

gráfica donde ponemos $k$ fichas indistinguibles unas de otras sobres los vértices de $G$ (a lo más una

por vértice). Luego pasamos de una configuracion de fichas a otra moviendo las fichas a lo largo de las

aristas de $G$. $F_k(G)$ es la gráfica de estas configuraciones.

La pregunta es si $G$ y $H$ son dos gráficas conexas, con más de $ k $ vértices, tales que $F_k(G)$ es isomorfa  $F_k(H)$ ¿Entonces $G$

es isomorfa a $H$? Me conformo con el caso $k=2$. Ah y ofrezco $500$ pesitos por su solución.

Comments

Supongo que no, pero igual pregunto. Estan etiquetados los vertices de $F_k(G)$? es decir, dado un vertice, sabemos  a cual subconjunto de vertices de $G$ pertence?

---

No, no están etiquetados.

---

Esto no es una respuesta y tal vez ya lo sepas, pero igual me parece interesante. Ademas sugiere cual podria ser una dificultad en el problema.

Sea $f:G\rightarrow H$ un isomorfismo, entonces $f$ induce un isomorfismo $f_*:F_k(G)\rightarrow F_k(H)$ de las graficas de fichas. El mapa $Iso(G,H)\rightarrow Iso(F_k(G), F_k(H))$ es en general no sobreyectivo. Es decir, hay isomorfismos de las graficas de fichas que no son inducidos por isomofismos de las graficas. Esto indica que en general $Iso(F_k(G), F_k(H))$ es mas grande que $Iso(G,H)$, en particular, podria suceder que el primero es no vacio y el segundo es vacio.

---

Sí de hecho el grupo de automorfismos de $G$ es subgrupo de automorfismo de las de fichas y a veces es propio. No lo había visto como tú. Es decir el levantar los isomorfimos entre dos gráficas a las de fichas. Lo último que dices sería un contraejemplo. Un caso donde $Iso(G,H)$ es vacío pero $Iso(F_k(G),F_k(H))$ no lo es.

Answer 1

¡Hola! Disculpa ¿tienes más hipótesis? Es que, por ejemplo:

Si no le pides conexidad o número de vértices mayor a dos, puedes tomar las dos gráficas simples no isomorfas con 2 vértices y ver que su gráfica de fichas es un sólo vértice en ambos casos.

Además, si no le pides a G y H ser simples, puedes tener 2 gráficas H y F con gráficas de fichas isomorfas, pero tales que F tenga algún par de aristas múltiples o un lazo que G no tenga, y eso impediría que fueran isomorfas.

Sé que son aclaraciones algo básicas para la mayoría de los ejercicios, pero si hay alguna otra hipótesis que falte, podría ser clave para resolver el problema.

Saludos.

Comments

Ah sí tienes razón!  Simple y con más de dos vértices. Ya con eso es suficiente.  Sí es disconexa la de fichas es disconexa. Ah bueno y sí cada componente conexo debe ser de al menos dos vértices.  Mejor ya conexa y con más de k vertices.

Gracias por la por la observación!