Coloquio del IMUNAM - C. U., febrero 2026

Resumen:

El problema del encaje de árboles en gráficas busca determinar cuáles son las condiciones mínimas que debe satisfacer una gráfica para garantizar que contiene, como subgráfica, a todo árbol con un número dado de aristas. Este problema se extiende de manera natural a digráficas, donde el objetivo es asegurar el encaje de todos los árboles orientados de un tamaño fijo.

Uno de los problemas abiertos centrales en esta línea es la conjetura de Erd\ős–Sós, la cual afirma que toda gráfica con n vértices y más de (k-1)n/2 aristas contiene a todo árbol con k aristas. Su análogo dirigido, conocido como la Conjetura de los Antiárboles, postula que toda digráfica con más de (k-1)n arcos contiene a todos los árboles antidirigidos con k arcos. En esta plática exploramos esta conjetura en el caso particular de las orugas (caterpillars), y presentamos avances recientes para familias más amplias de árboles antidirigidos.

Además, examinamos una dirección paralela de este problema, en la cual las condiciones de encaje se formulan en términos del semigrado mínimo de la digráfica huésped (es decir, el mínimo entre los grados de entrada y salida de sus vértices). En este contexto, mostramos que toda digráfica con semigrado mínimo al menos k/2, grado máximo de entrada y de salida al menos k, y sin ciclos orientados de longitud 4, contiene a todo árbol orientado con k arcos.