Probability, Combinatorics, . . . and Logic

Logic adds an additional dimension to the study of random combinatorial structures, seeking results for all properties expressible in a given logical structure. In the classic Galton-Watson tree (each node having Poisson mean c children) the property of being infinite is given by a tree recursion: T is finite iff all subtrees T(v), v a child of the root, are finite. This led Galton and Watson to the classic equation 1 − y = e^{−cy} for the probability y of being infinite. They saw that with c > 1 this has two solutions: y = 0 (we're doomed) and y = y_0 > 0 (no we're not). Fortunately (?) y_0 > 0 is the correct solution.

What about ‘some node has precisely 1 grandchild’? One can find a system of 2 equations in 2 unknowns yielding the probability. This time, however, the equations have a unique solution. Moreover, the solution is the fixed point of a contraction on a compact space.

Why the difference? Grandchild is expressible using quantification over vertices while Infinite is not. (For logicians: the distinction between 1st-order and monadic 2nd-order.) We show that any property expressible using only quantification over vertices behaves like Grandchild.

More complex logics give examples with more complex behavior. Consider ‘There exists an infinite full binary subtree, beginning at the root’. One gets an equation with 3 solutions, which have very distinct properties.

(Joint work with Moumanti Podder, Toby Johnson, Fiona Skerman)