Lugosi, GáborPereira, Alan S.2020-05-282020-05-282019Lugosi G, Pereira AS. Finding the seed of uniform attachment trees. Electron J Probab. 2019 Jan 22;24(18):1-15. DOI: 10.1214/19-EJP2681083-6489http://hdl.handle.net/10230/44844A uniform attachment tree is a random tree that is generated dynamically. Starting from a fixed “seed” tree, vertices are added sequentially by attaching each vertex to an existing vertex chosen uniformly at random. Upon observing a large (unlabeled) tree, one wishes to find the initial seed. We investigate to what extent seed trees can be recovered, at least partially. We consider three types of seeds: a path, a star, and a random uniform attachment tree. We propose and analyze seed-finding algorithms for all three types of seed trees.application/pdfengCopyright for all articles in EJP is CC BY 4.0.info:eu-repo/semantics/articlehttp://dx.doi.org/10.1214/19-EJP268Random treesUniform attachmentDiscrete probabilitySeedinfo:eu-repo/semantics/openAccess