The Strange Logic of Galton-Watson Trees

The Galton-Watson tree is a basic demographic model. The classic equation for a Galton-Watson tree being infinite has two solutions, only one of which is “correct.” What about other properties. (Example: Some node has precisely two children.) We show that when the property is what is called first order than there is a unique solution to the corresponding equation. We consider “tree automata” and the situation for monadic second order properties.

Speaker Details

Joel Spencer is a Professor of Mathematics and Computer Science at the Courant Institute, New York. His work is at the fecund intersection of Probability, Discrete Math and Logic, with a strong asymptotic flavor. He is a disciple of Paul Erdos. A new edition of His book (with Noga Alon) The Probabilistic Method will be published in December.

Date:
Speakers:
Joel Spencer
Affiliation:
Courant Institute