On the inducibility of rooted trees
Date
2018-12
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING : Die digtheid van verskynings van ’n vaste boom in ’n groter boom word ondersoek vir wortelbome sonder nodusse van uitgangsgraad 1 (ook bekend as topologiese bome). Gegewe ’n topologiese boom S met k blare en ’n heelgetal n > k, stel ons belang daarin om die maksimum en minimum aantal isomorfe kopieë van S in ’n willekeurige n-blaar topologiese boom T te bepaal. Die probleem word meer relevant wanneer n groot genoeg is. Dan word die doel om die bolimiet te bepaal van die verhouding van alle subversamelings van k blare van T wat ’n kopie van S voorstel, as die grootte van die boom T ba oneindig strewe. Hierdie maksimum word in die limiet die indusibiliteit van S genoem. Ons ondersoek die indusibiliteit in topologiese bome oor die algemeen: ons belangrikste fokus word egter op topologiese bome met beperkte grade geplaas wat ons d-êre bome noem — dit word gevind dat daar ’n eksplisiete verband bestaan tussen die indusibiliteit in topologiese bome en die indusibiliteit in d-êre bome. Ons bewys dat die indusibiliteit van elke boom streng positief is en bepaal ook die eksplisiete waarde daarvan vir sommige spesiale bome, naamlik sterre, binere ruspes, volledige d-êre bome en meer algemeen ewe êre bome. Verdere eienskappe soos hoeveel die indusibiliteit asimptoties van die maksimum digtheid verskil, word ook bestudeer. In die besonder lewer ons resultate ’n bevestigende antwoord op ’n bestaande vermoede oor die indusibiliteit van binere bome. Ons beantwoord ook (ten minste met ’n benadering) ’n oop vraag oor die indusibiliteit van ’n sekere binêre boom met vyf blare — ’n deel hiervan word deur middel van ’n algoritmiese benadering gedoen. Laastens beskou ons die probleem om die asimptotiese minimum aantal kopiee van ’n d-êre boom te vind. Vir die minimum is die situasie heel anders as die vir die maksimum; ons wys dat in die graad- beperkte konteks die onderlimiet van die verhouding van alle subversamelings van k blare van T wat ’n kopie van S voorstel as die grootte van T na oneindig strewe net vir binere ruspes (’n binêre boom met die eienskap dat ’n gewortelde pad oorbly as alle blare verwyder word) positief is. Dit stel ons in staat om ’n eksplisiete ondergrens vir hierdie limiethoeveelheid af te lei.
AFRIKAANSE OPSOMMING : Die digtheid van verskynings van ’n vaste boom in ’n groter boom word ondersoek vir wortelbome sonder nodusse van uitgangsgraad 1 (ook bekend as topologiese bome). Gegewe ’n topologiese boom S met k blare en ’n heelgetal n > k, stel ons belang daarin om die maksimum en minimum aantal isomorfe kopieë van S in ’n willekeurige n-blaar topologiese boom T te bepaal. Die probleem word meer relevant wanneer n groot genoeg is. Dan word die doel om die bolimiet te bepaal van die verhouding van alle subversamelings van k blare van T wat ’n kopie van S voorstel, as die grootte van die boom T ba oneindig strewe. Hierdie maksimum word in die limiet die indusibiliteit van S genoem. Ons ondersoek die indusibiliteit in topologiese bome oor die algemeen: ons belangrikste fokus word egter op topologiese bome met beperkte grade geplaas wat ons d-êre bome noem — dit word gevind dat daar ’n eksplisiete verband bestaan tussen die indusibiliteit in topologiese bome en die indusibiliteit in d-êre bome. Ons bewys dat die indusibiliteit van elke boom streng positief is en bepaal ook die eksplisiete waarde daarvan vir sommige spesiale bome, naamlik sterre, binere ruspes, volledige d-êre bome en meer algemeen ewe êre bome. Verdere eienskappe soos hoeveel die indusibiliteit asimptoties van die maksimum digtheid verskil, word ook bestudeer. In die besonder lewer ons resultate ’n bevestigende antwoord op ’n bestaande vermoede oor die indusibiliteit van binere bome. Ons beantwoord ook (ten minste met ’n benadering) ’n oop vraag oor die indusibiliteit van ’n sekere binêre boom met vyf blare — ’n deel hiervan word deur middel van ’n algoritmiese benadering gedoen. Laastens beskou ons die probleem om die asimptotiese minimum aantal kopiee van ’n d-êre boom te vind. Vir die minimum is die situasie heel anders as die vir die maksimum; ons wys dat in die graad- beperkte konteks die onderlimiet van die verhouding van alle subversamelings van k blare van T wat ’n kopie van S voorstel as die grootte van T na oneindig strewe net vir binere ruspes (’n binêre boom met die eienskap dat ’n gewortelde pad oorbly as alle blare verwyder word) positief is. Dit stel ons in staat om ’n eksplisiete ondergrens vir hierdie limiethoeveelheid af te lei.
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Topological trees, Trees (Graph theory), Topology, Binary trees, UCTD