Let $\mathcal{T}$ be an unrooted binary tree with $n$ distinctly labelled leaves. Deriving its name from the field of phylogenetics, a convex character on $\mathcal{T}$ is simply a partition of the leaves such that the minimal spanning subtrees induced by the blocks of the partition are mutually disjoint. In earlier work Kelk and Stamoulis (Advances in Applied Mathematics 84 (2017), pp. 34–46) defined $g_k(\mathcal{T})$ as the number of convex characters where each block has at least $k$ leaves. Exact expressions were given for $g_1$ and $g_2$, where the topology of $\mathcal{T}$ turns out to be irrelevant, and it was noted that for $k \geq 3$ topological neutrality no longer holds. In this article, for every $k \geq 3$ we describe tree topologies achieving the maximum and minimum values of $g_k$ and determine corresponding expressions and exponential bounds for $g_k$. Finally, we reflect briefly on possible algorithmic applications of these results.
@article{10_37236_10589,
author = {Steven Kelk and Ruben Meuwese},
title = {Sharp upper and lower bounds on a restricted class of convex characters},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/10589},
zbl = {1486.05043},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10589/}
}
TY - JOUR
AU - Steven Kelk
AU - Ruben Meuwese
TI - Sharp upper and lower bounds on a restricted class of convex characters
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10589/
DO - 10.37236/10589
ID - 10_37236_10589
ER -
%0 Journal Article
%A Steven Kelk
%A Ruben Meuwese
%T Sharp upper and lower bounds on a restricted class of convex characters
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10589/
%R 10.37236/10589
%F 10_37236_10589
Steven Kelk; Ruben Meuwese. Sharp upper and lower bounds on a restricted class of convex characters. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10589
