Seminario de Grafos “La conjetura de Erdős–Sós”

Speaker: Alonso Núñez (DIM UChile)

Abstract: La conjetura de Erdős–Sós, formulada en 1963, afirma que todo grafo con grado medio mayor estricto a $k-1$ contiene como subgrafo todo árbol con $k$ aristas. A pesar de la sencillez de su enunciado, el problema permaneció abierto durante más de seis décadas y dio lugar a numerosos resultados parciales, versiones aproximadas y nuevas técnicas para el estudio del embebimiento de árboles en grafos densos. En esta presentación hablaremos brevemente sobre algunos de los principales hitos en la historia de la conjetura y luego estudiamos una demostración reciente obtenida por GPT-6 Astra, que resuelve el problema general mediante un argumento de conteo que evita tanto el lema de regularidad como los métodos probabilísticos.

Hora/lugar: Jueves 8 Octubre, 10.30 sala John con Neumann