Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
On the inducibility of rooted trees
Thesis (PhD)--Stellenbosch University, 2018.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2018
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613870220115968 |
|---|---|
| access_status_str | Open Access |
| author | Dossou-Olory, Audace Amen Vioutou |
| author2 | Wagner, Stephan |
| author_browse | Dossou-Olory, Audace Amen Vioutou Wagner, Stephan |
| author_facet | Wagner, Stephan Dossou-Olory, Audace Amen Vioutou |
| author_sort | Dossou-Olory, Audace Amen Vioutou |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (PhD)--Stellenbosch University, 2018. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/104847 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:43:00.621Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2018 |
| publishDateRange | 2018 |
| publishDateSort | 2018 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/104847 On the inducibility of rooted trees Dossou-Olory, Audace Amen Vioutou Wagner, Stephan Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics. Topological trees Trees (Graph theory) Topology Binary trees UCTD Thesis (PhD)--Stellenbosch University, 2018. 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. Doctoral 2018-10-12T08:06:03Z 2018-12-07T06:47:40Z 2018-10-12T08:06:03Z 2018-12-07T06:47:40Z 2018-12 Thesis http://hdl.handle.net/10019.1/104847 en_ZA Stellenbosch University xiv, 157 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Topological trees Trees (Graph theory) Topology Binary trees UCTD Dossou-Olory, Audace Amen Vioutou On the inducibility of rooted trees |
| title | On the inducibility of rooted trees |
| title_full | On the inducibility of rooted trees |
| title_fullStr | On the inducibility of rooted trees |
| title_full_unstemmed | On the inducibility of rooted trees |
| title_short | On the inducibility of rooted trees |
| title_sort | on the inducibility of rooted trees |
| topic | Topological trees Trees (Graph theory) Topology Binary trees UCTD |
| url | http://hdl.handle.net/10019.1/104847 |
| work_keys_str_mv | AT dossouoloryaudaceamenvioutou ontheinducibilityofrootedtrees |