Resumen

Los grafos expansores han sido ampliamente estudiados por sus diversas aplicaciones en la matemática y computación; ya que son grafos regulares que distribuyen la información de manera muy eficiente. La constante de expansión mide esta capacidad, y es una pregunta natural cuál es el valor óptimo de esa constante y si es posible construir grafos que alcancen este óptimo. De mucho interés también es el caso bipartito, que tiene aplicaciones en compressive sensing y teoría de códigos.

En esta charla mostraremos el progreso realizado en conjunto con Mauricio Velasco (UDELAR) y Marcelo Fiori (UDELAR) en esta dirección: Introduciremos la noción de expansores bipartitos óptimos, que tienen la propiedad de alcanzar la mejor constante de expansión para conjuntos de un cierto tamaño; y probaremos una caracterización de ellos a través de su cintura/girth (ciclo de menor tamaño). Luego veremos la existencia de estos grafos usando el método probabilístico, estudiando modelos de intersección de rectas y puntos en espacios finitos; lo que nos da una construcción aleatoria pero computacionalmente verificable.

La charla será autocontenida así que están todos cordialmente invitados.