First order logic of random sparse structures

Abstract

(English) This work is dedicated to the study several models of random structures from the perspective of first-order logic. We prove that the asymptotic probabilities of first-order statements converge in a general model of random structures with linear density, extending previous results by Lynch. Additionally, we give an application of this result to the random SAT problem. We also inspect the set of limiting probabilities of first-order properties in sparse binomial graphs, binomial d-uniform hypergraphs and graphs with given degree sequences. In particular, we characterize the conditions under which this set of asymptotic probabilities is dense in the interval [0, 1]. Finally, we introduce the question of whether preservation theorems, namely Los-Tarski Theorem and Lyndon’s Theorem, hold in a probabilistic sense in various models of random graphs. We obtain several positive results in different regimes of the binomial random graph and uniform graphs from addable minor-closed classes.

(Español) Este trabajo está dedicado al estudio de varios modelos de estructuras aleatorias desde el punto de vista de la lógica de primer orden. Demostramos que las probabilidades asintóticas de las propiedades de primer orden convergen en un modelo general de estructuras aleatorias con densidade linear, generalizando resultados previos de Lynch. Damos también una aplicación de este resultado al estudio de instancias aleatorias del problema SAT. Además, inspeccionamos el conjunto de probabilidades límite relacionadas con las sentencias de primer orden en el régimen esparso de los grafos binomiales, hipergrafos d-uniformes y grafos con secuencias de grados dadas. En particular, caracterizamos las situaciones en las que este conjunto de probabilidades límite es denso en el intervalo [0,1]. Por último, introducimos la pregunta sobre si los teoremas de preservación de la lógica de primer orden, concretamente los teoremas de Los-Tarski y de Lyndon, se cumplen en varios modelos de grafos aleatorios. Obtenemos múltiples resultados positivos para diferentes régimenes de grafo aleatorio binomial y para grafos aleatorios de clases sumables cerradas por menores.