Admin CliCours
FONCTIONNELLES DE COÛT DE GRANDS ARBRES ALÉATOIRES (UNIFORMES ET SIMPLEMENT GÉNÉRÉS)
Ordered trees have many applications in various fields such as computer science for data structures or in biology for genealogical or phylogenetic trees of extant species. Related to those applications, the study of large trees has attracted some attention. In this paper, we shall consider asymptotics in the global regime for general additive functionals of large trees corresponding to the Catalan model and some simply generated trees. Such additive functionals give indexes of trees which are used in computer science, physics or biology to summarize some properties of trees.For instance, the total path length P (t) of a tree t, see (3.1) and (3.2) for a precise definition, which sums the distances to the root of all nodes, in the context of binary search trees, counts the number of key comparisons needed by Hoare’s sorting algorithm Quicksort to sort a list of randomly permuted items, see Rösler [172]. Its convergence towards the Airy distribution was first established by Takács [183], see also Aldous [9, 10] and Janson [113] for binary trees under the Catalan model, Régnier [166], Rösler [172] for binary search trees under the random permutation model (RPM) and Fill and Kapur [90, 91] for m-ary search definition, which sums the distances between all pairs of nodes of t, was introduced by the chemist Wiener [193] in 1947. It was initially defined as the number of bonds between all pairs of atoms in an acyclic molecule. It also plays an important role in physicochemical properties of chemical structures (boiling points, heat of formation, crystal defects, …), see Dobrynin, Entringera and Gutman [66] or Trinajstic [185], chapter 10. Its asymptotics has been studied by Janson [113] for binary trees under the Catalan model, Neininger [152] for binary search trees under the RPM and recursive trees and Janson [113] for simply generated trees.
The study of additive functionals associated with monomials, that is f (x) = xin (3.4), with > 0, is interesting because many usual additive functionals can be expressed in terms of those elementary functionals. Moreover, a phase transition in the limiting behavior appears when varies, see Fill and Kapur [89], Fill and Janson [88] for uniform binary trees, Neininger [151] for binary search trees under RPM and Fill and Kapur for m-ary trees [90, 91].Additive functionals also appears naturally for the study of phylogenetic trees (rooted binary trees with n labeled leaves corresponding to species and n 1 internal vertices). When the number of species in studies of phylogenies grows, it can be interesting to look at the shapes of these trees through indices. Among these indices, we can cite the Sackin index S(t) of a tree t, see definition (3.7), introduced in 1972 by Sackin [175] and also studied in computer science for binary search trees (named as external path length), see Régnier [166] and Rösler [172]. Blum, François and Janson [27] studied its asymptotics. We can also consider the Colless index C(t) of a tree t, see definition (3.6), introduced by Colless [50] in 1982. Its asymptotics have also been studied by by Blum, François and Janson [27]. The cophenetic index Co(t) of a tree t was introduced in 2013 by Mir, Rosseló and Rotger [146] and Cardona, Mir and Rosseló [42] who studied its limiting behavior.
We stress that additive functionals in the local regime, such as the total size, the number of leaves, the number of protected nodes, the number of sub-trees or the shape functional (take f (x) = log(x)=x in (3.1) or b= log(n) in (3.4)) are not covered by our results. See Wagner [191], Holmgren et Janson [108], Janson [115] and Ralaivaosaona and Wagner [165] for asymptotic results in the local regime.(f ) when t belongs to a certain class of trees and jtj goes to infinity. We shall consider two classes of trees: the binary trees (and more precisely the Catalan model) and some simply generated trees.However the asymptotics will be the same as the one for F when the toll function is a power function, see Remark 3.9. We complete the examples of the previous section for binary trees.
Télécharger le document complet
