On the inducibility of small trees
The quantity that captures the asymptotic value of the maximum number of appearances of a given topological tree (a rooted tree with no vertices of outdegree $1$) $S$ with $k$ leaves in an arbitrary tree with sufficiently large number of leaves is called the inducibility of $S$. Its precise value is...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5381/pdf |
| _version_ | 1827323723738251264 |
|---|---|
| author | Audace A. V. Dossou-Olory Stephan Wagner |
| author_facet | Audace A. V. Dossou-Olory Stephan Wagner |
| author_sort | Audace A. V. Dossou-Olory |
| collection | DOAJ |
| description | The quantity that captures the asymptotic value of the maximum number of
appearances of a given topological tree (a rooted tree with no vertices of
outdegree $1$) $S$ with $k$ leaves in an arbitrary tree with sufficiently large
number of leaves is called the inducibility of $S$. Its precise value is known
only for some specific families of trees, most of them exhibiting a symmetrical
configuration. In an attempt to answer a recent question posed by Czabarka,
Sz\'ekely, and the second author of this article, we provide bounds for the
inducibility $J(A_5)$ of the $5$-leaf binary tree $A_5$ whose branches are a
single leaf and the complete binary tree of height $2$. It was indicated before
that $J(A_5)$ appears to be `close' to $1/4$. We can make this precise by
showing that $0.24707\ldots \leq J(A_5) \leq 0.24745\ldots$. Furthermore, we
also consider the problem of determining the inducibility of the tree $Q_4$,
which is the only tree among $4$-leaf topological trees for which the
inducibility is unknown. |
| first_indexed | 2024-04-25T01:57:02Z |
| format | Article |
| id | doaj.art-0b06712aede049adb0dd4230048664f9 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:02Z |
| publishDate | 2019-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0b06712aede049adb0dd4230048664f92024-03-07T15:40:07ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-10-01vol. 21 no. 4Combinatorics10.23638/DMTCS-21-4-135381On the inducibility of small treesAudace A. V. Dossou-OloryStephan WagnerThe quantity that captures the asymptotic value of the maximum number of appearances of a given topological tree (a rooted tree with no vertices of outdegree $1$) $S$ with $k$ leaves in an arbitrary tree with sufficiently large number of leaves is called the inducibility of $S$. Its precise value is known only for some specific families of trees, most of them exhibiting a symmetrical configuration. In an attempt to answer a recent question posed by Czabarka, Sz\'ekely, and the second author of this article, we provide bounds for the inducibility $J(A_5)$ of the $5$-leaf binary tree $A_5$ whose branches are a single leaf and the complete binary tree of height $2$. It was indicated before that $J(A_5)$ appears to be `close' to $1/4$. We can make this precise by showing that $0.24707\ldots \leq J(A_5) \leq 0.24745\ldots$. Furthermore, we also consider the problem of determining the inducibility of the tree $Q_4$, which is the only tree among $4$-leaf topological trees for which the inducibility is unknown.https://dmtcs.episciences.org/5381/pdfmathematics - combinatorics05c05, 05c07, 05c30, 05c60 |
| spellingShingle | Audace A. V. Dossou-Olory Stephan Wagner On the inducibility of small trees Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05c05, 05c07, 05c30, 05c60 |
| title | On the inducibility of small trees |
| title_full | On the inducibility of small trees |
| title_fullStr | On the inducibility of small trees |
| title_full_unstemmed | On the inducibility of small trees |
| title_short | On the inducibility of small trees |
| title_sort | on the inducibility of small trees |
| topic | mathematics - combinatorics 05c05, 05c07, 05c30, 05c60 |
| url | https://dmtcs.episciences.org/5381/pdf |
| work_keys_str_mv | AT audaceavdossouolory ontheinducibilityofsmalltrees AT stephanwagner ontheinducibilityofsmalltrees |