Department of
Applied
Mathematics

Quantifier-free Convergence of Structures

Lucas Hosseini

Abstract

The notion of L-convergence for graphs (in relation with homomorphism densities for fixed patterns and Szemeredi's regularity lemma) introduced by Lovasz et al. got increasingly studied over the past 10 years. Recently, Nesetril and Ossona de Mendez introduced a general framework to study the limits of structures based on the converging probability for the structures of the sequence to verify any formula of a given fragment of logic for a random assignment of free variables. In this context, a sequence is quantifier-free convergent (or QF-convergent) if the probability of any equation being satisfied converges. We will give examples, and show how the QF-convergence of tree-orders can be related to the L-convergence of a generalization of cographs.