From trees to seeds: on the inference of the seed from large trees in the uniform attachment model (Q2405129)

This paper studies the inference of the seed in large trees in the uniform attachment model. For \(2\leq k\leq n\) and a tree \(S\) with \(k\) vertices, let \(UA(k,S)=S\) and \(UA(n+1,S)\) be formed by adding a new vertex \(u\) and adding a new edge \(uv\), where \(v\) is chosen uniformly at random among vertices of \(UA(n,S)\) independently. For two seed trees \(S\) and \(T\), define the total variation distance \(\delta(S,T)=\lim_{n\rightarrow\infty}TV(UA(n,S),UA(n,T))\). By constructing statistics that measure global balancedness properties of growing trees, the authors show that \(\delta(S,T)\) is always positive for any \(S\) and \(T\) non-isomorphic with at least 3 vertices. Moreover, for any fixed tree \(T\), \(\lim_{k\rightarrow\infty}\delta(S_k,T)=1\), where \(S_k\) is the \(k\)-vertex star.