Abstract:

Dado un grupo finito $G$ y un sistema de generadores $C$ de $G$, el grafo de Cayley de $G$ respecto de $C$ tiene como vértices los elementos de $G$ y como aristas $\{g, g \cdot c\}$ donde $g \in G$ y $c \in C$. Los grafos de Cayley son objetos centrales en la teoría geométrica y combinatoria de grupos.

En 1978 Babai propuso el problema de determinar si existe una constante $k$ tal que todo grafo de Cayley respecto de un sistema minimal de generadores admite una coloración (propia) con a lo sumo $k$ colores y, en 1994, conjeturó una respuesta negativa.

En esta charla veremos por qué bastan 3 colores para colorear los grafos de diversas familias de grupos, que incluyen los grupos nilpotentes y diedrales. En contraste, mostraremos grupos resolubles y sistemas generadores minimales de los mismos tales que su correspondiente grafo de Cayley no es 3-coloreable.

Asimismo, discutiremos algunas variantes del problema también propuestas por Babai.

Los resultados de esta charla han sido obtenidos en colaboración con Kolja Knauer.