First order logic of random sparse structures

Autor/a

Larrauri Borroto, Lázaro Alberto

Director/a

Noy Serrano, Marcos

Data de defensa

2023-03-03

Pàgines

91 p.



Departament/Institut

Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística

Programa de doctorat

DOCTORAT EN MATEMÀTICA APLICADA (Pla 2012)

Resum

(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.

Paraules clau

Random graphs; First-order logic; Limit laws; Preservation theorems; Random SAT; Random structures; Sparse graphs; Minor-closed classes

Matèries

519.1 - Teoria general de l'anàlisi combinatòria. Teoria de grafs

Àrea de coneixement

Àrees temàtiques de la UPC::Matemàtiques i estadística

Documents

TLALB1de1.pdf

767.0Kb

 

Drets

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by/4.0/

Aquest element apareix en la col·lecció o col·leccions següent(s)