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 - https://doi.org/10.23638/DMTCS-21-4-13
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(A5) of the 5-leaf binary tree A5 whose branches are a single leaf and the complete binary tree of height 2. It was indicated before that J(A5) appears to be `close' to 1/4. We can make this precise by showing that 0.24707J(A5)0.24745. Furthermore, we also consider the problem of determining the inducibility of the tree Q4, 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 1260 times.
    This article's PDF has been downloaded 320 times.