First order probabilities for Galton-Watson trees

Moumanti Podder, Joel Spencer

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In the regime of Galton-Watson trees, first order logic statements are roughly equivalent to examining the presence of specific finite subtrees. We consider the space of all trees with Poisson offspring distribution and show that such finite subtrees will be almost surely present when the tree is infinite. Introducing the notion of universal trees, we show that all first order sentences of quantifier depth k depend only on local neighbourhoods of the root of sufficiently large radius depending on k. We compute the probabilities of these neighbourhoods conditioned on the tree being infinite. We give an almost sure theory for infinite trees.

Original languageEnglish (US)
Title of host publicationA Journey through Discrete Mathematics
Subtitle of host publicationA Tribute to Jiri Matousek
PublisherSpringer International Publishing
Pages711-734
Number of pages24
ISBN (Electronic)9783319444796
ISBN (Print)9783319444789
DOIs
StatePublished - Jan 1 2017

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)
  • Economics, Econometrics and Finance(all)
  • Business, Management and Accounting(all)

Fingerprint Dive into the research topics of 'First order probabilities for Galton-Watson trees'. Together they form a unique fingerprint.

  • Cite this

    Podder, M., & Spencer, J. (2017). First order probabilities for Galton-Watson trees. In A Journey through Discrete Mathematics: A Tribute to Jiri Matousek (pp. 711-734). Springer International Publishing. https://doi.org/10.1007/978-3-319-44479-6_29