Scaling limits and influence of the seed graph in preferential attachment trees

par Prof. Ioan MANOLESCU (Université de Genève)

mardi 9 déc. 2014, 14:30 → 15:30 Europe/Paris

Centre de conférences Marilyn et James Simons (I.H.E.S.)

We investigate two aspects of large random trees built by linear preferential attachment, also known in the literature as Barabasi-Albert trees. Starting with a given tree (called the seed), a random sequence of trees is built by adding vertices one by one, connecting them to one of the existing vertices chosen randomly with probability proportional to its degree. Bubeck, Mossel and Racz conjectured that the law of the trees obtained after adding a large number of vertices still carries information about the seed from which the process started. We confirm this conjecture using an observable based on the number of ways of embedding a given (small) tree in a large tree obtained by preferential attachment. Next we study scaling limits of such trees. Since the degrees of vertices of a large preferential attachment tree are much higher than its diameter, a simple scaling limit would lead to a non locally compact space that fails to capture the structure of the object. Yet, for a planar version of the model, a much more convenient limit may be defined via its loop tree. The limit is a new object called the Brownian tree, obtained from the CRT by a series of quotients.