Grafos y Teoría de números

Ponente(s): César Ernesto Rodríguez Angón

Los grafos, o gráficas, nos permiten representar diversos tipos de relaciones entre objetos mediante vértices y aristas y obtener una buena imagen de la situación global a partir de relaciones locales. De esta forma, podemos construir grafos utilizando relaciones en los enteros como la divisibilidad o que la multiplicación de un par de números sea de cierta forma. Traducir un problema de teoría de números a uno de teoría de grafos nos permite aprovechar la estructura combinatoria de los grafos para obtener resultados sobre los enteros. Ejemplos sencillos pueden verse en problemas del tipo olimpiadas de matemáticas. De igual forma, la teoría espectral de grafos y el método probabilístico dan paso una buena conexión entre grafos y teoría analítica de números. La conexión es útil también en el sentido contrario. Un ejemplo destacable aparece en la construcción de gráficas de Ramanujan, famosas, entre otras cosas, por sus aplicaciones en códigos de corrección de errores y, potencialmente, criptografía post-cuántica. En esta plática revisaremos algunos ejemplos de la conexión entre estas dos ramas, entre los que se destaca el uso de los grafos expansores.