FO and EMSO logic of rooted trees and graphs

Monadic second order sentence about a finite structure is a formal sentence with quantification over first order variables (elements of the structure) and sets of elements. In existential sentences (EMSO), only existential quantifiers over set variables are allowed. The first part of the talk is devoted to logic of rooted trees. First, we consider Galton-Watson (GW) tree with Poisson(λ) offspring distribution, though most of the results can be extended to very general distributions. We give a complete description of the probabilities Pλ[A] of all possible first order (FO) sentences A conditioned on the survival of the GW tree. Second, we consider the problem of expressing finiteness of a rooted tree in EMSO and prove that it is not expressible (in contrast, infiniteness is expressible in EMSO). We also solve this problem for GW trees. The second part of the talk is devoted to FO and EMSO logic of graphs. It is very well known that, for every first order sentences, it is either true for almost all graphs or false for almost all graphs. In contrast, such a “zero-one law” fails for EMSO. We study quantifier complexities of EMSO sentences without zero-one law. Joint work with Joel Spencer, Alexander Holroyd, Avi Levy.