Doctoral Degrees (Mathematical Sciences)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/852

Browse

Browsing Doctoral Degrees (Mathematical Sciences) by Author "Dossou-Olory, Audace Amen Vioutou"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    On the inducibility of rooted trees
    (Stellenbosch : Stellenbosch University, 2018-12) Dossou-Olory, Audace Amen Vioutou; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics.
    ENGLISH ABSTRACT : The density of appearances of a fixed tree in a larger tree is examined for rooted trees without vertices of outdegree 1 (also known as topological trees). Given a topological tree S with k leaves and an integer n > k, we are interested in finding the maximum and minimum number of isomorphic copies of S in an arbitrary n-leaf topological tree T. The problem becomes more relevant when n is sufficiently large. Then the goal becomes to determine the limit superior of the proportion of all subsets of k leaves of the set of leaves of T that induce a copy of S as the size of the tree T grows to infinity. This limiting maximum quantity is called the inducibility of S. We investigate the inducibility in topological trees at large: our major focus, however, is placed on bounded degree topological trees which we call d-ary trees—it is found that there is an explicit identity between the inducibility in topological trees and the inducibility in d-ary trees. We prove that the inducibility of every tree is strictly positive and also determine its explicit value for some special families of trees, namely stars, binary caterpillars, complete d-ary trees and more generally even d-ary trees. Further properties such as how much the inducibility differs asymptotically from the maximum density, are also studied. In particular, our results provide an affirmative answer to an existing conjecture on the inducibility of binary trees. We also solve (at least approximately) another open question concerning the inducibility of a binary tree with five leaves—part of this is done by means of an algorithmic approach. Finally, we consider the problem of finding the asymptotic minimum number of copies of a d-ary tree. For the minimum, the situation is quite different from that of the maximum; we show that, in the degree-restricted context, the limit inferior of the proportion of all subsets of k leaves of the set of leaves of T that induce a copy of S as the size of T tends to infinity is positive for binary caterpillars (a binary tree with the property that a rooted path remains upon removal of all leaves) only. This allows us to derive an explicit lower bound on this limiting quantity.