The First Order World of Galton-Watson Trees

Consider the classic Galton-Watson tree T=Tc in which each node, independently, has Poisson mean c children. The probability f(c) that Tc is infinite is continuous, but it is not differentiable at the critical point c=1. Let, for example, g(c) be the probability that some node has precisely one child. This g(c) has derivatives of all orders and, indeed, is real analytic. We show that for a wide variety of properties, called First Order properties, the probability h(c) will be real analytic and, furthermore, can be found as the unique fixed point of a contraction Ψ on a compact set D. We introduce a notion of a property being “rapidly determined” and its effect on the corresponding probability function.

Speaker Details

Joel Spencer is a Professor at NYU, well known for key contributions to the probabilistic method in Combinatorics. For more details, see https://en.wikipedia.org/wiki/Joel_Spencer and http://www.cs.nyu.edu/spencer/

Series:
Microsoft Research Talks
Date:
Speakers:
Joel Spencer
Affiliation:
Courant Institute, NYU

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks