First order probabilities for Galton-Watson trees

DOI10.1007/978-3-319-44479-6_29zbMATH Open1381.60082arXiv1510.08832OpenAlexW1851722155MaRDI QIDQ4604396FDOQ4604396

Authors: Moumanti Podder, Joel Spencer 

Publication date: 26 February 2018

Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1510.08832

Recommendations

• Galton-Watson probability contraction
• Stochastic ordering of infinite binomial Galton-Watson trees
• Analyticity for rapidly determined properties of Poisson Galton-Watson trees
• Local limits of large Galton-Watson trees rerooted at a random vertex
• Stochastic ordering of infinite geometric Galton-Watson trees

zbMATH Keywords

Galton-Watson treesPoisson offspring distributionuniversal trees

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Zero-one laws (60F20)

Cites Work

• Random graphs and complex networks. Volume 1
• The strange logic of random graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)

Cited In (4)

• Probability of first return on Cayley trees
• Continuous phase transitions on Galton–Watson trees
• Analyticity for rapidly determined properties of Poisson Galton-Watson trees
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves

This page was built for publication: First order probabilities for Galton-Watson trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604396)