Sesión Matemática DiscretaEl problema de Hamilton-Waterloo: historia, variaciones y últimos avances
Adrián Pastine
Departamento de Matemática, Universidad Nacional de San Luis, e IMASL (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El problema de Hamilton-Waterloo es un problema clásico de descomposición de grafos, que yace en la intersección entre la teoría de grafos y la teoría de diseños combinatorios. Este tipo de problemas tienen aplicaciones en la construcción de otros objetos combinatorios y en el diseño de experimentos.
Un $k$-factor de un grafo es un subgrafo generador $k$-regular. En particular, un $1$-factor es un matching perfecto, y un $2$-factor es una unión disjunta de ciclos. Denotamos por $K_n^*$ al grafo completo $K_n$ de orden $n$ si $n$ es impar, y a $K_n$ menos las aristas de un $1$-factor si $n$ es par. Dados dos $2$-factores de $K_n^*$, $F_1$ y $F_2$, el problema de Hamilton-Waterloo estudia para qué valores de $r$ y $s$ es posible particionar las aristas de $K_n^*$ en $r$ copias de $F_1$ y $s$ copias de $F_2$. La mayor parte del estudio de este problema se realizó para el caso uniforme, que es cuando todos los ciclos de $F_1$ tiene un tamaño fijo $x$, y todos los ciclos de $F_2$ tienen un tamaño fijo $y$. De todos modos, quedan aún casos uniformes por estudiar, en particular cuando $x$ e $y$ son coprimos. En lo que respecta al caso no uniforme, hay muy poco hecho, por lo que queda aún mucho camino por recorrer.
En esta charla daremos un recuento histórico del problema, pasando por los resultados más importantes y presentando el estado del arte actual. Presentaremos algunas construcciones que hacen uso de grupos y de cuasigrupos, y algunas técnicas de producto de grafos y de duplicado de vértices. Hablaremos también de algunas variaciones del problema, como el problema de Hamilton-Waterloo de la luna de miel, y el problema de Hamilton-Waterloo sobre grafos equipartitos completos.