Pseudofinitud y medibilidad de la teoría de los grafos acíclicos infinito-regulares

Este trabajo de grado tiene como objetivo estudiar las principales propiedades modelo-teóricas de tres clases de grafos: los grafos aleatorios (RG), los bosques infinitos r-regulares (Tr), y los bosques infinito-regulares (Tinf). En primer lugar, se recopilan las propiedades conocidas en la literatura del área: la teoría de Tr es fuertemente minimal, mientras que Tinf es omega-estable de rango de Morley omega. Además, se puede dar una descripción de la clausura algebraica mediante propiedades combinatóricas: en Tr la clausura algebraica de un conjunto es su clausura conexa, mientras que en Tinf es su clausura convexa. La siguiente propiedad por revisar es la de ser pseudofinito. El ejemplo prototípico de un grafo pseudofinito es el grafo aleatorio y, al igual que este, las teorías Tr y Tinf también son pseudofinitas. Esta conclusión se debe a la existencia de dos familias de grafos finitos cuyos ultraproductos son modelos de Tr y de Tinf respectivamente. Una de las razones para estudiar estructuras pseudofinitas es que existe una noción de cardinalidad pseudofinita para los conjuntos definibles. En general, no se puede dar una caracterización de cuáles son las posibles cardinalidades en estos ultraproductos, pero existen algunos casos en los que se pueden dar descripciones explícitas, y este es el caso de las llamadas "estructuras medibles". El principal resultado de este tipo que se conoce se debe a Pillay, el cual aplica directamente al caso de Tr. Además, en este trabajo de grado logramos obtener un resultado similar en Tinf: si M es un modelo de Tinf que es un ultraproducto de grafos finitos regulares y X es un conjunto definible, entonces existe un polinomio p(t,s) en dos variables con coeficientes enteros tal que p(a,|M|)=|X|, donde "a" es la regularidad de M. Entre los ejemplos más importantes de estructuras medibles se encuentran los ultraproductos de clases asintóticas, entre las cuales se encuentra la clase de grafos de Paley.

• Autores: Robles Carmona, Melissa Verónica
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2021
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: spa
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/53474
• Acceso en línea: http://hdl.handle.net/1992/53474
• Palabra clave: Teoría de grafos; Grafos aleatorios; Matemáticas
• Rights: openAccess
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/