En este curso de postgrado orientado a la investigación, estudiaremos algoritmos para la partición y agrupación de gráficos, construcciones de gráficos de expansión y análisis de recorridos aleatorios. Estos son tres temas que se basan en los mismos antecedentes matemáticos y que tienen varias conexiones importantes: por ejemplo, es posible encontrar agrupaciones de gráficos a través de paseos aleatorios, y es posible utilizar el enfoque de programación lineal para la partición de gráficos como una forma de estudiar los paseos aleatorios.
Estudiaremos la teoría de los gráficos espectrales, que explica cómo ciertas propiedades combinatorias de los gráficos están relacionadas con los valores propios y los vectores propios de la matriz de adyacencia, y la utilizaremos para describir y analizar los algoritmos espectrales para la partición y agrupación de los gráficos. La teoría de los gráficos espectrales será una herramienta importante en el resto del curso. También discutiremos otros enfoques para la partición de gráficos mediante la programación lineal y la programación semidefinida. Luego estudiaremos construcciones de gráficos de expansión, que son gráficos con propiedades de pseudoaleatoriedad muy fuertes, que son útiles en muchas aplicaciones, incluyendo la criptografía, la teoría de la complejidad, los algoritmos y las estructuras de datos, y la teoría de la codificación. Por último, estudiaremos el tiempo de mezcla de los paseos aleatorios, un problema que surge en varias aplicaciones, incluido el análisis del tiempo de convergencia de ciertos algoritmos aleatorios, como el algoritmo de Metrópolis.
Carga de trabajo
alrededor de 8 horas por semana
Requisitos previos
álgebra lineal, probabilidad discreta y algoritmos