Audace A. V. Dossou-Olory ; Stephan Wagner - On the inducibility of small trees

dmtcs:5381 - Discrete Mathematics & Theoretical Computer Science, October 17, 2019, vol. 21 no. 4 -
On the inducibility of small treesArticle

Authors: Audace A. V. Dossou-Olory ; Stephan Wagner

    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ékely, 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.

    Volume: vol. 21 no. 4
    Section: Combinatorics
    Published on: October 17, 2019
    Accepted on: September 2, 2019
    Submitted on: April 15, 2019
    Keywords: Mathematics - Combinatorics,05C05, 05C07, 05C30, 05C60

    Consultation statistics

    This page has been seen 1126 times.
    This article's PDF has been downloaded 253 times.