Alberto Larrauri
defended his PhD thesis First Order Logic of Random Sparse Structures on March 03, 2023.
The thesis was produced within the UPC doctoral program on Applied Mathematics and his advisor was Marc Noy.
Starting May 2023, he will be a postdoctoral researcher at the University of Oxford in the group of Standa Živný.
Thesis summary
In the case of graphs, first order (FO) logic speaks about adjacencies using quantification over vertices and Bolean connectives. A natural question in this area is: given a sequence of random graphs Gn, does the limit probability that Gn satisfy P exist for every FO property P? When the answer is yes, we say that Gn satisfies a FO convergence law. As a follow-up to the last question, we can also ask what are the possible values of those limit probabilities. We may also be interested in studying the FO properties P that hold in Gn with high probability (w.h.p.). This thesis makes contributions in all these directions, focusing on sparse (as opposite to dense) random structures.
In the first part, published in [1], we look at a binomial model of random relational structures. We prove that a FO convergence law holds in this model when each relation is expected to grow linearly with the number of elements in the structure. Moreover, we show that the limit probability of each FO statement is given by an analytic expression in terms of the density of each relation. We extend this result to more complex models where symmetry and anti-reflexivity constraints are imposed on the random structure. Finally, we give an application our convergence results to the study of random SAT, suggested by Albert Atserias. A line of research here tries to establish the existence of efficient algorithms that accurately decide satisfiability of random CNF formulas with high probability. Our contribution here states, roughly, that if P is a FO statement that implies unsatisfiability of CNF formulas, then w.h.p. P does not hold in random CNF formulas with linear number of clauses.
In the second part we consider several random models where a FO convergence law is known to hold, and we study the set L of limiting probabilities of FO statements. More concretely, we consider the linear ranges of binomial random graphs and binomial random uniform hypergraphs [2], as well as of random graphs with given degree sequences. Our main result here is that L is dense in the whole interval [0,1] exactly when the random model in question contains some cycle with asymptotic probability exceeding 1/2. Otherwise the closure of L is a finite union of closed intervals with some ‘gaps’ in between.
The final chapter is devoted to the study of probabilistic versions of FO preservation theorems. These are classical results that relate semantic and syntactic classes of FO sentences. For instance, Lyndon’s Theorem states that any monotone sentence is equivalent to some positive sentence, and Ło´s-Tarski Theorem states that any sentence closed under extensions is equivalent to some existential sentence. Crucially, these results are stated for the class of all structures (both finite and infinite), and fail when restricted to finite structures. We define probabilistic versions of those two preservation theorems where logical equivalence is replaced by almost sure equivalence, and ask whether those new results hold in several random graphs, obtaining multiple positive results. We consider the binomial random graph at the connectivity threshold, in the linear range, and in the sublinear range. Additionally, we also look at uniform random graphs from addable minor-closed classes.
Selected Publication: [2].
References
[1] Alberto Larrauri, Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas, Journal of Logic and Computation 31 (2021), 444-472.
[2] Alberto Larrauri, Tobias Müller, Marc Noy, Limiting probabilities of first order properties of random sparse graphs and hypergraphs, Random Structures and Algorithms 60 (2022), 506-526.