Grandes desvíos para procesos de exploración de grafos aleatorios

El Área de Matemática del PEDECIBA invita a la defensa de tesis de doctorado de la estudiante  Valeria Goicoechea Jackson.

Orientadores:

Dra.Paola Bermolen
Dr. Matthieu Jonckheere

Integración del tribunal:

Dra. Paola Bermolen
Dra. Karine Bertin
Dr. Pablo Groisman
Dr. José R. León
Dr. Alain Roualt

Resumen de la tesis: 

En esta tesis nos enfocamos en el estudio de los grandes desvíos (GD) para sucesiones de procesos de Markov que describen el comportamiento de ciertos algoritmos de exploración greedy sobre grafos aleatorios con el fin de construir conjuntos independientes en esos grafos. Nos centramos en cuatro aspectos de los GD para estos procesos:
- Probar los GD para las trayectorias de dichos procesos de Markov,
- Deducir el límite fluido a partir de la función de tasa del GD,
- Encontrar la trayectoria que minimiza la función de tasa sobre un conjunto de trayectorias,
- Concluir resultados de GD para el tamaño del conjunto independiente construido mediante el algoritmo greedy.
Para demostrar el PGD (Principio de Grandes Desvíos) para las sucesiones de procesos de interés, utilizamos la estrategia propuesta por [Feng & Kurtz, 2006] para el estudio de GD de procesos estocásticos, la que se basa en la convergencia de semigrupos no lineales asociados a dichos procesos.
La tesis se desarrolla de la siguiente manera. Comenzamos presentando brevemente el trabajo de [Feng & Kurtz, 2006] en el contexto de procesos de Markov sobre espacios de estados compactos. En el Capítulo 3, analizamos los cuatro aspectos de los GD mencionados antes para una sucesión de procesos de Markov relacionados a un algoritmo greedy definido sobre un grafo de Erdös-Rényi dado con el objetivo de construir un conjunto independiente, cuando el tamaño del grafo tiene a infinito. En el Capitulo 4, repetimos este análisis para un algoritmo en el que simultáneamente se construye un grafo d-regular y un conjunto independiente en ese grafo. Finalmente, en el Capítulo 5 extendemos los resultados del capitulo anterior para grafos aleatorios uniformes más generales.
Además de presentar resultados originales sobre los GD para los procesos de interés, creemos que el aporte de este trabajo consiste en mostrar de forma entendible la herramienta poderosa propuesta en el trabajo de [Feng & Kurtz, 2006] para el estudio de GD de procesos, con posibles aplicaciones a diversas áreas.