The 20th Northwest Probability Seminar: First Order Logic on Galton-Watson Trees

October 20, 2018
Moumanti Podder | University of Washington

The 20th Northwest Probability Seminar, a one-day mini-conference organized by the University of Washington, the Oregon State University, the University of British Columbia, the University of Oregon, and Microsoft Research, was held on October 20, 2018. The conference will be hosted at Microsoft, supported by Microsoft Research and the Pacific Institute for the Mathematical Sciences (PIMS).

Talk Title: First Order Logic on Galton-Watson Trees

Speaker: Moumanti Podder (University of Washington)

Abstract: This talk will focus on the rooted Galton-Watson (GW) tree, and we shall limit ourselves to Poisson (λ) offspring distributions. We discuss the first order (FO) language, derived from mathematical logic, on rooted trees. FO sentences describe finite structures inside the tree. We analyze the probabilities of FO properties under the GW measure, and obtain these probabilities as fixed points of contracting distributional maps. Moreover, we show that the probabilities of FO sentences, conditioned on survival of the GW tree, are expressible as nice functions of λ and pλ, the survival probability.

Time permitting, we shall briefly touch on some of the recently concluded work on second order logic on random rooted trees. Joint work with Joel Spencer.

View presentation slides here: https://www.microsoft.com/en-us/research/wp-content/uploads/2018/11/First-Order-Logic-on-Galton-Watson-Trees-SLIDES.pdf