• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






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

+6 votos
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.
preguntado por Ruy Fabila (300 puntos) Sep 6, 2013 en Preguntas
editado por Ruy Fabila Sep 7, 2013
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.

1 Respuesta

+3 votos
¡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.
respondido por Jorge Moreno M (600 puntos) Sep 7, 2013
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!
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...