Cursos

El mazo de un grafo: una introducción al problema de reconstrucción

El problema de reconstrucción de grafos pregunta hasta qué punto un grafo queda determinado por la colección de todos sus subgrafos inducidos obtenidos al eliminar un vértice. Esta colección, conocida como el mazo del grafo, contiene información parcial sobre la estructura original, pero pierde la identidad de los vértices eliminados. La famosa conjetura de reconstrucción, formulada a partir de los trabajos de Kelly y Ulam, afirma que todo grafo finito simple con al menos tres vértices queda determinado, salvo isomorfismo, por su mazo.

En este minicurso introduciremos los conceptos básicos del problema de reconstrucción y estudiaremos algunos de los primeros parámetros que pueden recuperarse a partir del mazo, tales como el número de vértices, el número de aristas, la secuencia de grados y la conexidad. Luego presentaremos una de las herramientas centrales del área, el lema de Kelly, que permite reconstruir el número de copias de todo subgrafo propio fijo. Como aplicación principal, analizaremos la reconstrucción de árboles, uno de los primeros resultados clásicos de la teoría, originalmente probado por Kelly.

El curso estará dirigido a estudiantes e investigadores con conocimientos previos de teoría de grafos. No se requerirá familiaridad previa con el problema de reconstrucción. La exposición combinará definiciones, ejemplos, resultados clásicos e ideas de demostración, con el objetivo de ofrecer una entrada accesible a un problema abierto central de la teoría de grafos.

El minicurso constará de tres encuentros de una hora. En el primer encuentro se presentarán el mazo de un grafo, la conjetura de reconstrucción y los primeros invariantes reconstruibles. En el segundo encuentro se estudiará el lema de Kelly y algunas de sus consecuencias. En el tercer encuentro se discutirá la reconstrucción de árboles y se ofrecerá un breve panorama de resultados conocidos, variantes del problema y preguntas abiertas.

Parte de la bibliografía de referencia está incluida en:

• P. J. Kelly, A congruence theorem for trees, Pacific Journal of Mathematics 7 (1957), 961–968.

•  J. A. Bondy and R. L. Hemminger, Graph reconstruction: a survey, Journal of Graph Theory 1 (1977), 227–268.

• J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts 54, Cambridge University Press, 2003.

• S. Monikandan, Reconstruction of graphs, in Recent Applications in Graph Theory, IntechOpen, 2021.

TBD

TBD

Universidad Nacional de General Sarmiento

Universidad Nacional de San Luis

Universidad Nacional de Córdoba