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

Abstract

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.

The main purpose of this thesis is to study the main model-theoretic properties of three important graph theories: the random graph theory (RG), the infinite r-regular forest theory (Tr), and the infinite-regular forest theory (Tinf). Firstly, we gathered the main properties known in the area: the theory Tr is strongly minimal, while Tinf is omega-stable with Morley rank omega. Additionally, we can give a combinatorial description of the algebraic closure: in Tr the algebraic closure of any set coincides with its connected closure, while in Tinf it is equivalent to its convex closure. The next property to check is the pseudofiniteness of the theories. The prototypical example of a pseudofinite graph is the Random Graph and, just like it, the theories Tr and Tinf are also pseudofinite. This conclusion is due to the existence of two families of finite graphs which ultraproducts are models of Tr and Tinf respectively. One of the main reasons to study pseudofinite structures is that there exists a notion of pseudofinite cardinality for the definable sets. In general, no characterization can be given of which are the possible infinite cardinalities in the ultraproducts, but in some cases explicit descriptions can be given uniformly on the parameters, these are called ¿measurable structures¿. The principal result of this kind known in the area is due to Pillay, which applies directly to Tr. Furthermore, in this project we obtained a similar result for Tinf: if M is a model of Tinf and it is also an ultraproduct of finite regular graphs, then for every definable set X there exists a polynomial p(t,s) in two variables with integer coefficients, such that p(a,|M|)=|X|, where "a" represents the regularity of M. Among the most important examples of measurable structures are the ultraproducts of asymptotic classes, where we can find the class of Paley graphs.