Cursos

Universidad Nacional de General Sarmiento

Universidad Nacional de San Luis

Universidad Nacional de Córdoba

Resumen

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.

Resumen

La descomposición de grafos estudia cuándo las aristas de un grafo pueden particionarse en copias de subgrafos dados. Uno de los problemas más naturales en este contexto consiste en determinar cuándo el grafo completo puede descomponerse en copias de un grafo fijo G, dando lugar a la noción de G-diseño. Este tipo de problemas conecta naturalmente la teoría de grafos con los diseños combinatorios y ha motivado el desarrollo de numerosas técnicas de construcción.

En este minicurso presentaremos una introducción a algunos de los conceptos, resultados y métodos fundamentales del área. Comenzaremos estudiando G-diseños y las condiciones necesarias para su existencia. A través de ejemplos concretos analizaremos descomposiciones en triples, matchings y otros grafos pequeños. Como uno de los resultados fundamentales del área, presentaremos el teorema de Wilson, que establece condiciones asintóticas para la existencia de G-diseños.

A continuación, estudiaremos algunas construcciones clásicas basadas en aritmética modular y grupos cíclicos. Estas técnicas permiten obtener descomposiciones de grafos completos y grafos circulantes en familias de subgrafos dadas, y constituyen una herramienta fundamental en gran parte de la investigación actual sobre descomposición de grafos.

Finalmente, si el tiempo lo permite, introduciremos los problemas de Oberwolfach y Hamilton-Waterloo, dos problemas clásicos que pueden formularse en términos de descomposiciones resolubles del grafo completo en ciclos. 

El curso está dirigido a estudiantes avanzados e investigadores con conocimientos básicos de teoría de grafos. No se supondrá experiencia previa en teoría de diseños. El objetivo es ofrecer una primera aproximación a los problemas de descomposición de grafos, combinando ejemplos concretos, técnicas constructivas y algunos de los problemas más representativos del área.

Resumen

Es usual asignar estructuras u objetos algebraicos a objetos combinatorios, por ejemplo, el grupo de automorfismos de un grafo o las matrices de adyacencia e incidencia. En este caso, veremos cómo asignar grafos a estructuras algebraicas y así obtener información estructural de dichas estructuras a partir de los grafos.

Se introducirán y estudiarán grafos relacionados con estructuras algebraicas conmutativas: grupos, anillos y cuerpos finitos. Más precisamente, estudiaremos grafos de Cayley, denotados usualmente por Cay(G,S), donde (G,+) es un grupo abeliano y S es un subconjunto de G-{0}. Este grafo tiene como conjunto de vértices a G y hay una flecha de a hacia b en el grafo si b=a+s con s un elemento de S. Estos grafos son muy útiles para estudiar los "word problems" en presentaciones de grupos, así como también problemas de teoría aditiva de números, como el problema de Waring.

Durante el curso haremos foco especial en los siguientes casos:

1. Grafos definidos sobre anillos conmutativos con unidad, G_{R}(k)=Cay(R,U_{R}(k)), donde U_{R}(k) es el conjunto {x^{k}: x \in R*}, usualmente llamados k-ésimo grafo unitario de Cayley.  

2. Grafos definidos sobre cuerpos finitos Cay(F_q, U_k), donde F_q es el cuerpo de q elementos y U_{k}={x^k: x \in F_{q}*}. 

Estudiaremos la conexidad, así como también la bipartitud en estos grafos y la relación con su espectro.

Cuando k=2 y q =1 (mod 4), este grafo es el llamado grafo de Paley; fue introducido para obtener valores concretos en el estudio de los números de Ramsey de tipo diagonal; además, presenta una estructura combinatoria relacionada con la teoría de diseños. 

Haremos énfasis en la manera en que muchos problemas clásicos en teoría de cuerpos finitos: ecuaciones diagonales, periodos gaussianos, sumas exponenciales de tipo Gauss-Jacobi y el problema de Waring pueden ser traducidos de manera natural al estudiar ciertos invariantes del grafo  Cay(F_q, U_k). También mencionaremos la relación espectral entre estos grafos y los códigos cíclicos irreducibles.

Finalmente, mostraremos cómo muchas descomposiciones algebraicas sobre anillos finitos se traducen de manera natural a descomposiciones del grafo, de manera que los grafos G_{R}(k) pueden ser escritos como productos de Kronecker de grafos  Cay(F_q, U_k). Lo que permitirá enunciar y obtener muchos invariantes de G_{R}(k) en términos de  Cay(F_q, U_k).