Dependencies

A vertex \(m\) lies between \(u\) and \(v\) when every walk from \(u\) to \(v\) meets \(m\). A ray is a map \(\mathbb {N}\to V\) isometric onto its image and a line is such a map \(\mathbb {Z}\to V\). A hair at \(c\) of depth \(h\) is a component \(P\) of the complement of \(\{ c\} \) with \(d(v,c)\leq h\) for every \(v\in P\) and equality for some \(v\). Finally \(\mathrm{Ray}\) is \(\mathbb {N}\) with the path-graph structure.

Write \(\mathbb {P}^{\mathrm{s}}\) for the field measure conditioned on survival and \(\mathbb {P}^{\mathrm{b}}\) for it conditioned on extinction. The skeleton degree of a field is the number of children of the root founding an infinite subtree.

The decoration of a skeleton vertex is its offspring count \(j\), its number \(k\) of surviving children, and its dying subtrees indexed by rank.

The extinction probability of \(\theta \) is

the least fixed point of \(f\) in \([0,1]\).

The generating function of \(\theta \) is \(f(s)=\sum _{j=0}^{J}\theta _j s^j\).

An offspring law with support bound \(J\) is a sequence \(\theta =(\theta _j)_{j\geq 0}\) of nonnegative reals vanishing above \(J\) and summing to one. Its mean is \(m=\sum _j j\, \theta _j\), and \(\theta \) is subcritical, critical or supercritical according as \(m{\lt}1\), \(m=1\) or \(m{\gt}1\).

The truncated progeny \(Z_k\) is the number of vertices of the sample within the first \(k\) generations.

A map \(f\colon V\to V'\) is a \(D\)-quasi-isometry from \(G\) to \(G'\) when

for all \(x,y\), and every vertex of \(G'\) lies within \(D\) of the image. Two graphs are quasi-isometric when such a map exists for some \(D\).

The reduced law is the Harris–Sevastyanov transform \(\tilde\theta _k=\bigl(\sum _j\theta _j\binom {j}{k}(1-q)^kq^{\, j-k}\bigr)/(1-q)\) for \(k\geq 1\) and \(\tilde\theta _0=0\); the conjugate law is \(\hat\theta _j=\theta _jq^{\, j}/q\). Both are offspring laws with the same support bound.

A field of offspring counts is a map \(c\colon \mathcal{N}(N)\to \mathbb {N}\). The sample of \(c\) is the subtree in which each vertex \(v\) keeps its first \(c(v)\) children,

The field survives when \(\mathcal{T}(c)\) is infinite.

The field measure on \(\mathcal{N}(N)\to \mathbb {N}\) is the infinite product of copies of \(\theta \), one per vertex. Its pushforward along \(\mathcal{T}\) is the law of the Galton–Watson tree of \(\theta \), a measure on subtrees for the \(\sigma \)-algebra generated by the vertex events \(\{ T : v\in T\} \).

The skeleton of a sample is the set of its vertices whose residual subtree is infinite.

A subtree of \(\mathcal{N}(N)\) is a prefix-closed set of words, taken as a term of Mathlib’s Descriptive.tree. The residual subtree of \(T\) at \(v\) is \(T_v=\{ w : vw\in T\} \).

Fix \(N\in \mathbb {N}\). A vertex of the ambient tree \(\mathcal{N}(N)\) is a finite word over the alphabet \(\{ 0,\dots ,N-1\} \); the root is the empty word \(\emptyset \) and the children of \(v\) are the words \(v j\) with \(j{\lt}N\). The wedge \(v\wedge w\) of two vertices is their longest common prefix, and the graph metric of \(\mathcal{N}(N)\) is

The residual subtree of \(\mathcal{T}(c)\) at a vertex of the sample is the sample of the shifted field, and \(\mathcal{T}(c)\) decomposes into its root together with the samples hanging off the children of the root.

\(q\in [0,1]\), \(f(q)=q\), and \(q\leq s\) for every fixed point \(s\in [0,1]\) of \(f\).

\(q=0\) if and only if \(\theta _0=0\); in particular \(\theta _0{\gt}0\) forces \(q{\gt}0\).

\(f(1)=1\), \(f(0)=\theta _0\), \(f\) maps \([0,1]\) into itself monotonically, and \(f'(1)=m\).

Two fields agreeing at the vertices of one of their samples cut out the same tree. Hence the probability that the sample is a prescribed finite tree \(T\) is \(\prod _{v\in T}\theta _{c(v)}\), and it is at least \(p^{\lvert T \rvert }\) whenever every offspring weight along \(T\) is at least \(p\).

For a subcritical law there are \(s,y{\gt}1\) with \(s f(y)=y\).

Writing \(F_k(s)=\mathbb {E}\bigl[s^{Z_k}\bigr]\), one has \(F_{k+1}(s)=s\, f(F_k(s))\), and any \(y{\gt}1\) with \(s f(y)=y\) bounds every \(F_k(s)\).

A skeleton vertex has a child in the skeleton, and hence carries a ray, an isometric copy of \(\mathbb {N}\) inside the sample.

Let \(f\) be a \(D\)-quasi-isometry between trees. Every vertex separating \(f(u)\) from \(f(v)\) lies within \(D\) of the image of a walk from \(u\) to \(v\).

Unconditionally, the root has exactly \(k\) surviving children with probability

and the value at \(k=0\) is \(f(q)=q\).

The subtraction defining \(d\) does not truncate, \(d(v,w)=0\) exactly when \(v=w\), and \(d\) satisfies the triangle inequality. A vertex and one of its children are at distance one.

The wedge \(v\wedge w\) is a prefix of both \(v\) and \(w\), and every common prefix of \(v\) and \(w\) is a prefix of \(v\wedge w\).

If \(J\leq N\), then \(\mathbb {P}(\mathcal{T}\text{ finite})=q\).

A tree carrying hairs of unbounded depth is not quasi-isometric to a tree all of whose vertices lie within a bounded distance of a line.

If \(J\leq N\) and \(q{\gt}0\), a sample conditioned on extinction has the law of the Galton–Watson tree of the conjugate law.

Conditioned on survival, probe the skeleton on a finite prefix-closed set \(F\) of addresses and constrain the decoration of each probed vertex. The mass factorises into one weight per vertex,

each dying subtree entering through the Galton–Watson law of the conjugate law.

If \(J\leq N\) and \(q{\lt}1\), the re-addressed skeleton of a sample conditioned on survival has the law of the Galton–Watson tree of the reduced law.

For a subcritical offspring law there is \(\sigma {\gt}1\) with \(\mathbb {E}\bigl[\sigma ^{\lvert \mathcal{T} \rvert }\bigr]{\lt}\infty \). The same holds for the size of a bush once the conjugate law is subcritical.

If \(m{\gt}1\) then \(q{\lt}1\).

A tree carrying three rays that pairwise meet only in their common initial vertex is not quasi-isometric to \(\mathrm{Ray}\).