Conjetura de reconstrucción

Problema sin resolver en matemáticas :

¿Los gráficos están determinados únicamente por sus subgráficos?

(más problemas sin resolver en matemáticas)

De manera informal, la conjetura de reconstrucción en la teoría de grafos dice que los grafos están determinados únicamente por sus subgrafos. Se debe a Kelly ^[1] y Ulam . ^{[2] [3]}

Declaraciones formales

Un gráfico y la baraja asociada de subgráficos con un solo vértice eliminado. Nótese que algunas de las cartas muestran gráficos isomorfos.

Dado un grafo , un subgrafo con vértice eliminado de es un subgrafo formado al eliminar exactamente un vértice de . Por definición, es un subgrafo inducido de . ${\displaystyle G=(V,E)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Para un grafo , la baraja de G , denotada , es el multiconjunto de clases de isomorfismo de todos los subgrafos de vértices eliminados de . Cada grafo en se llama carta . Se dice que dos grafos que tienen la misma baraja son hipomórficos . ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle G}$ ${\displaystyle D(G)}$

Con estas definiciones la conjetura puede enunciarse así:

• Conjetura de reconstrucción: Dos grafos hipomórficos cualesquiera en al menos tres vértices son isomorfos.

(El requisito de que los gráficos tengan al menos tres vértices es necesario porque ambos gráficos en dos vértices tienen las mismas cubiertas).

Harary ^[4] sugirió una versión más fuerte de la conjetura:

• Conjetura de reconstrucción de conjuntos: Dos gráficos cualesquiera en al menos cuatro vértices con los mismos conjuntos de subgráficos sin vértices son isomorfos.

Dado un gráfico , un subgráfico con arista eliminada de es un subgráfico formado al eliminar exactamente una arista de . ${\displaystyle G=(V,E)}$ ${\displaystyle G}$ ${\displaystyle G}$

Para un grafo , la baraja de aristas de G , denotada , es el multiconjunto de todas las clases de isomorfismo de subgrafos de aristas eliminadas de . Cada grafo en se llama carta de aristas . ${\displaystyle G}$ ${\displaystyle ED(G)}$ ${\displaystyle G}$ ${\displaystyle ED(G)}$

• Conjetura de reconstrucción de aristas: (Harary, 1964) ^[4] Dos gráficos cualesquiera con al menos cuatro aristas y que tengan las mismas capas de aristas son isomorfos.

Propiedades reconocibles

En el contexto de la conjetura de reconstrucción, una propiedad de un grafo se considera reconocible si se puede determinar la propiedad a partir de la estructura de un grafo. Las siguientes propiedades de los grafos son reconocibles:

• Orden del gráfico – El orden de un gráfico , se reconoce a partir de que el multiconjunto contiene cada subgráfico de creado al eliminar un vértice de . Por lo tanto ^[5] ${\displaystyle G}$ ${\displaystyle |V(G)|}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle |V(G)|=|D(G)|}$
• Número de aristas del grafo – El número de aristas en un grafo con vértices, es reconocible. Primero note que cada arista de ocurre en miembros de . Esto es cierto por la definición de que asegura que cada arista se incluye cada vez que cada uno de los vértices con los que incide se incluye en un miembro de , por lo que una arista ocurrirá en cada miembro de excepto en los dos en los que se eliminan sus puntos finales. Por lo tanto, donde es el número de aristas en el i ésimo miembro de . ^[5] ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle |E(G)|}$ ${\displaystyle G}$ ${\displaystyle n-2}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle |E(G)|=\sum {\frac {q_{i}}{n-2}}}$ ${\displaystyle q_{i}}$ ${\displaystyle D(G)}$
• Secuencia de grados – La secuencia de grados de un grafo es reconocible porque el grado de cada vértice es reconocible. Para encontrar el grado de un vértice —el vértice ausente del i- ésimo miembro de —, examinaremos el grafo creado al eliminarlo, . Este grafo contiene todas las aristas que no inciden con , por lo que si es el número de aristas en , entonces . Si podemos determinar el grado de cada vértice en el grafo, podemos determinar la secuencia de grados del grafo. ^[5] ${\displaystyle G}$ ${\displaystyle v_{i}}$ ${\displaystyle D(G)}$ ${\displaystyle G_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle G_{i}}$ ${\displaystyle |E(G)|-q_{i}=\deg(v_{i})}$
• (Conectividad entre vértices) – Por definición, un grafo está conectado entre vértices cuando al eliminar cualquier vértice se crea un grafo conectado entre vértices; por lo tanto, si cada carta es un grafo conectado entre vértices, sabemos que el grafo original estaba conectado entre vértices. También podemos determinar si el grafo original estaba conectado, ya que esto es equivalente a que dos de ellos estén conectados. ^[5] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle G_{i}}$
• Polinomio de Tutte
• Polinomio característico
• Planaridad
• Los tipos de árboles de expansión en un gráfico
• Polinomio cromático
• Ser un gráfico perfecto o un gráfico de intervalo , o ciertas otras subclases de gráficos perfectos ^[6]

Verificación

Brendan McKay ha verificado tanto la conjetura de reconstrucción como la de reconstrucción de conjuntos para todos los gráficos con un máximo de 13 vértices . ^{[7] [8]}

En un sentido probabilístico, Béla Bollobás ha demostrado que casi todos los grafos son reconstruibles. ^[9] Esto significa que la probabilidad de que un grafo elegido al azar sobre vértices no sea reconstruible tiende a cero, ya que tiende a infinito. De hecho, se ha demostrado que no sólo son reconstruibles casi todos los grafos, sino que, de hecho, no es necesario todo el mazo para reconstruirlos: casi todos los grafos tienen la propiedad de que existen tres cartas en su mazo que determinan de forma única el grafo. ${\displaystyle n}$ ${\displaystyle n}$

Familias de grafos reconstruibles

La conjetura ha sido verificada para un número infinito de clases de gráficos (y, trivialmente, sus complementos).

• Grafos regulares ^[10] - Los grafos regulares son reconstruibles mediante la aplicación directa de algunos de los hechos que se pueden reconocer a partir del mazo de un grafo. Dado un grafo -regular y su mazo , podemos reconocer que el mazo es de un grafo regular al reconocer su secuencia de grados. Examinemos ahora un miembro del mazo , . Este grafo contiene una cierta cantidad de vértices con un grado de y vértices con un grado de . Podemos agregar un vértice a este grafo y luego conectarlo a los vértices de grado para crear un grafo -regular que es isomorfo al grafo con el que comenzamos. Por lo tanto, todos los grafos regulares son reconstruibles a partir de sus mazos. Un tipo particular de grafo regular que es interesante es el grafo completo. ^[5] ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle G_{i}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$
• Árboles ^[10]
• Grafos desconectados ^[10]
• Gráficas de intervalos unitarios ^[6]
• Grafos separables sin vértices finales ^[11]
• Gráficos planos máximos
• Gráficos maximalistas exteriores-planares
• Gráficos extraplanares
• Bloqueos críticos

Reducción

La conjetura de reconstrucción es verdadera si todos los gráficos 2-conectados son reconstruibles. ^[12]

Dualidad

La conjetura de reconstrucción de vértices obedece a la dualidad de que si se puede reconstruir a partir de su mazo de vértices , entonces su complemento se puede reconstruir a partir de la siguiente manera: comience con , tome el complemento de cada carta para obtener , use esto para reconstruir , luego tome el complemento nuevamente para obtener . ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle G'}$ ${\displaystyle D(G')}$ ${\displaystyle D(G')}$ ${\displaystyle D(G)}$ ${\displaystyle G}$ ${\displaystyle G'}$

La reconstrucción de aristas no obedece a ninguna de esa dualidad: de hecho, para algunas clases de gráficos reconstruibles por aristas no se sabe si sus complementos son reconstruibles por aristas.

Otras estructuras

Se ha demostrado que en general no son reconstruibles:

• Dígrafos : Se conocen infinitas familias de dígrafos no reconstruibles, incluidos los torneos (Stockmeyer ^[13] ) y los no torneos (Stockmeyer ^[14] ). Un torneo es reconstruible si no está fuertemente conectado. ^[15] Se ha conjeturado una versión más débil de la conjetura de reconstrucción para los dígrafos, véase nueva conjetura de reconstrucción de dígrafos .
• Hipergrafos ( Kocay ^[16] ).
• Grafos infinitos . Si T es el árbol donde cada vértice tiene grado infinito numerable , entonces la unión de dos copias disjuntas de T es hipomórfica, pero no isomorfa, a T. ^[17 ]
• Grafos localmente finitos, que son grafos en los que cada vértice tiene un grado finito. La cuestión de la reconstructibilidad para árboles infinitos localmente finitos (la conjetura de Harary-Schwenk-Scott de 1972) fue un problema abierto desde hace mucho tiempo hasta 2017, cuando Bowler et al. encontraron un árbol no reconstruible de grado máximo 3. ^[18]

Véase también

• Nueva conjetura sobre la reconstrucción de dígrafos
• Simetría parcial

Lectura adicional

Para más información sobre este tema, véase la encuesta de Nash-Williams . ^[19]

Referencias

1. Kelly, PJ, Un teorema de congruencia para árboles, Pacific J. Math. 7 (1957), 961–968.
2. Ulam, SM, Una colección de problemas matemáticos, Wiley, Nueva York, 1960.
3. O'Neil, Peter V. (1970). "Conjetura de Ulam y reconstrucciones de grafos". Amer. Math. Monthly . 77 (1): 35–43. doi :10.2307/2316851. JSTOR  2316851.
4. Harary, F., Sobre la reconstrucción de un grafo a partir de una colección de subgrafos. En Teoría de grafos y sus aplicaciones (Proc. Sympos. Smolenice, 1963) . Publ. House Czechoslovak Acad. Sci., Praga, 1964, págs. 47–52.
5. Wall, Nicole. "La conjetura de la reconstrucción" (PDF) . Consultado el 31 de marzo de 2014 .
6. von Rimscha, M.: Reconstructibilidad y grafos perfectos. Matemáticas discretas 47 , 283–291 (1983)
7. McKay, BD, Los gráficos pequeños son reconstruibles, Australas. J. Combin. 15 (1997), 123–126.
8. McKay, Brendan (2022). "Reconstrucción de pequeños grafos y dígrafos". Austras. J. Combin . 83 : 448–457.
9. Bollobás, B., Casi todos los grafos tienen número de reconstrucción tres, J. Graph Theory 14 (1990), 1–4.
10. Harary, F. (1974), "Un estudio de la conjetura de reconstrucción", Graphs and Combinatorics , Lecture Notes in Mathematics , vol. 406, Springer, págs. 18-28, doi :10.1007/BFb0066431, ISBN 978-3-540-06854-9
11. Bondy, J.-A. (1969). "Sobre la conjetura de Ulam para grafos separables". Pacific J. Math . 31 (2): 281–288. doi : 10.2140/pjm.1969.31.281 .
12. Yang Yongzhi: La conjetura de reconstrucción es verdadera si todos los grafos 2-conexos son reconstruibles. Journal of graph theory 12 , 237–243 (1988)
13. Stockmeyer, PK, La falsedad de la conjetura de reconstrucción para torneos, J. Graph Theory 1 (1977), 19–25.
14. Stockmeyer, PK, Un censo de dígrafos no reconstruibles, I: seis familias relacionadas, J. Combin. Theory Ser. B 31 (1981), 232–239.
15. Harary, F. y Palmer, E., Sobre el problema de reconstruir un torneo a partir de subtorneos, Monatsh. Math. 71 (1967), 14–23.
16. Kocay, WL, Una familia de hipergrafos no reconstruibles, J. Combin. Theory Ser. B 42 (1987), 46–63.
17. Nash-Williams, C. St. JA; Hemminger, Robert (3 de diciembre de 1991). "Reconstrucción de grafos infinitos" (PDF) . Matemáticas discretas . 95 (1): 221–229. doi :10.1016/0012-365X(91)90338-3.
18. Bowler, N., Erde, J., Heinig, P., Lehner, F. y Pitz, M. (2017), Un contraejemplo de la conjetura de reconstrucción para árboles localmente finitos. Bull. London Math. Soc.. doi :10.1112/blms.12053
19. Nash-Williams, C. St. JA , El problema de reconstrucción, en Temas seleccionados en teoría de grafos , 205–236 (1978).