Tìtulo: «Propiedades lógicas de estructuras aleatorias»

Jurados: Inés Armendariz y Santiago Figueira

Resumen:

La ley 0-1 de Fagin establece que, para toda propiedad P expresable en la lógica de primer orden de grafos, la probabilidad de que un grafo aleatorio cumpla P tiende a 0 o a 1. En este trabajo exploraremos variaciones y generalizaciones del anterior resultado, con énfasis en versiones efectivas, es decir, con cotas en la velocidad de convergencia y la complejidad del problema de decisión asociado.