Sesión Álgebra, Teoría de Números y TopologíaTeoría de invariantes y la conjetura de reconstrucción de grafos
Gabriela Jeronimo
Universidad de Buenos Aires - CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
La conjetura de reconstrucción de grafos ([2],[5]) dice que todo grafo simple no dirigido $G$ con al menos tres vértices se puede reconstruir a partir del multiconjunto $\mathcal{D}(G)$ formado por (las clases de isomorfismos de) todos los grafos que se obtienen borrando un vértice $v$ de $G$ y todas las aristas incidentes en $v$; en otros términos, si $G$ y $G'$ son grafos tales que $\mathcal{D}(G) = \mathcal{D}(G')$, entonces $G$ y $G'$ son isomorfos.
Este problema ha sido ampliamente estudiado y, si bien la conjetura permanece abierta, se han obtenido resultados parciales, incluyendo la demostración de su validez para ciertas clases de grafos (árboles, grafos regulares, grafos completos, grafos disconexos, grafos planares maximales, entre otras [3]). Recientemente, un enfoque computacional permitió verificar que la conjetura vale para todos los grafos de hasta 13 vértices [4].
Presentaremos un trabajo en curso sobre una nueva formulación de la conjetura de reconstrucción para grafos con pesos sobre un cuerpo $\mathbb{K}$ por medio de teoría de invariantes. El conjunto de los grafos de $n$ vértices con pesos en $\mathbb{K}$ forma un $\mathbb{K}$-espacio vectorial $V_n$ y el anillo de invariantes $\mathbb{K}[V_n]^{S_n}$ de la acción del grupo simétrico $S_n$ permite determinar si dos grafos son isomorfos. Reformulamos la conjetura de reconstrucción de grafos como la pregunta de si ciertos subconjuntos de $\mathbb{K}[V_n]^{S_n}$ son conjuntos separantes, es decir, conjuntos de invariantes que permiten distinguir las órbitas de la acción del grupo. Resultados sobre cálculo de conjuntos separantes (ver [1]) dan lugar a un nuevo acercamiento computacional a la conjetura. Por otra parte, la caracterización algebraico-geométrica del problema permite obtener nuevas demostraciones de la conjetura para familias de grafos.
Trabajo en conjunto con: Emilie Dufresne (University of York, Reino Unido), Jenny Kenkel (Grinnell College, Estados Unidos), Haydee Lindo (Harvey Mudd College, Estados Unidos) y Nelly Villamizar (Swansea University, Reino Unido).
Referencias
[1] H. Derksen, G. Kemper, Computational invariant theory, Encyclopaedia of Mathematical Sciences, vol. 130, Springer, Heidelberg, 2015.
[2] P. Kelly, A congruence theorem for trees, Pacific J. Math 7 (1957), 961–968.
[3] J. Lauri and R. Scapellato. Topics in graph automorphisms and reconstruction. Cambridge University Press, 2016.
[4] B. McKay, Reconstruction of small graphs and digraphs, Australas. J. Comb. 83 (2022), 448–457.
[5] S. Ulam, A collection of mathematical problems, Wiley, 1960.