On the inducibility of small trees

zbMATH Open1432.05030arXiv1811.12010MaRDI QIDQ5207849FDOQ5207849

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

Publication date: 13 January 2020

Abstract: 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.24707ldotsleqJ(A_5)leq0.24745ldots$. 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.

Full work available at URL: https://arxiv.org/abs/1811.12010

Recommendations

• Inducibility of topological trees
• Further results on the inducibility of \(d\)-ary trees
• Inducibility of \(d\)-ary trees
• Inducibility in binary trees and crossings in random tanglegrams
• Inducibility and universality for trees

zbMATH Keywords

binary tree\(d\)-ary treeinducibilitymaximum densitytopological treeternary treeleaf-induced subtree

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex degrees (05C07) Enumeration in graph theory (05C30)

Cited In (5)

• Further results on the inducibility of \(d\)-ary trees
• Inducibility in binary trees and crossings in random tanglegrams
• Inducibility of \(d\)-ary trees
• Inducibility and universality for trees
• Inducibility of topological trees

This page was built for publication: On the inducibility of small trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207849)