First order probabilities for Galton-Watson trees

DOI10.1007/978-3-319-44479-6_29MaRDI QIDQ4604396zbMATH OpenOpenAlexFDO

Authors Moumanti Podder, Joel Spencer

Publication date 26 February 2018

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

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

zbMATH Keywords

Galton-Watson treesPoisson offspring distributionuniversal trees

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 1341924 (Why is no real title available?)
• Random graphs and complex networks. Volume 1
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strange logic of random graphs

Cited in

(7)

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

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)