The First Order World of Galton-Watson Trees


July 17, 2015


Joel Spencer


Courant Institute, NYU


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.


Joel Spencer

Joel Spencer is a Professor at NYU, well known for key contributions to the probabilistic method in Combinatorics. For more details, see and