TY - JOUR

T1 - Injective split systems

AU - Hellmuth, Marc

AU - Huber, Katharina T.

AU - Moulton, Vincent

AU - Scholz, Guillaume E.

AU - Stadler, Peter F.

N1 - Acknowledgements: This work was supported in part by the German Federal Ministry for Education and Research (BMBF 031L0164C, RNAProNet, to P.F.S.). The authors would like to thank the Institut Mittag-Leffler in Djursholm, Sweden for hosting the conference “Emerging Mathematical Frontiers in Molecular Evolution” in August 2022, where this work was finalized. They also thank the two reviewers for their careful reading of the manuscript.
Funding: Open Access funding enabled and organized by Projekt DEAL. This study was funded by Bundesministerium für Bildung und Forschung (No. BMBF 031L0164C).

PY - 2023/6/6

Y1 - 2023/6/6

N2 - A split system $\mathcal S$ on a finite set $X$, $|X|\ge3$, is a set of bipartitions or splits of $X$ which contains all splits of the form $\{x,X-\{x\}\}$, $x \in X$. To any such split system $\mathcal S$ we can associate the Buneman graph $\mathcal B(\mathcal S)$ which is essentially a median graph with leaf-set $X$ that displays the splits in $\mathcal S$. In this paper, we consider properties of injective split systems, that is, split systems $\mathcal S$ with the property that $\med_{\mathcal B(\mathcal S)}(Y) \neq \med_{\mathcal B(\mathcal S)}(Y')$ for any 3-subsets $Y,Y'$ in $X$, where $\med_{\mathcal B(\mathcal S)}(Y)$ denotes the median in $\mathcal B(\mathcal S)$ of the three elements in $Y$ considered as leaves in $\mathcal B(\mathcal S)$. In particular, we show that for any set $X$ there always exists an injective split system on $X$, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph $\mathcal B(\mathcal S)$ needs to become in order for a split system $\mathcal S$ on $X$ to be injective. We do this by introducing a quantity for $|X|$ which we call the injective dimension for $|X|$, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on $X$ can be represented using Buneman graphs.

AB - A split system $\mathcal S$ on a finite set $X$, $|X|\ge3$, is a set of bipartitions or splits of $X$ which contains all splits of the form $\{x,X-\{x\}\}$, $x \in X$. To any such split system $\mathcal S$ we can associate the Buneman graph $\mathcal B(\mathcal S)$ which is essentially a median graph with leaf-set $X$ that displays the splits in $\mathcal S$. In this paper, we consider properties of injective split systems, that is, split systems $\mathcal S$ with the property that $\med_{\mathcal B(\mathcal S)}(Y) \neq \med_{\mathcal B(\mathcal S)}(Y')$ for any 3-subsets $Y,Y'$ in $X$, where $\med_{\mathcal B(\mathcal S)}(Y)$ denotes the median in $\mathcal B(\mathcal S)$ of the three elements in $Y$ considered as leaves in $\mathcal B(\mathcal S)$. In particular, we show that for any set $X$ there always exists an injective split system on $X$, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph $\mathcal B(\mathcal S)$ needs to become in order for a split system $\mathcal S$ on $X$ to be injective. We do this by introducing a quantity for $|X|$ which we call the injective dimension for $|X|$, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on $X$ can be represented using Buneman graphs.

KW - median graph

KW - split system

KW - Buneman graph

KW - Split system

KW - Median graph

UR - http://www.scopus.com/inward/record.url?scp=85154028305&partnerID=8YFLogxK

U2 - 10.1007/s00373-023-02660-w

DO - 10.1007/s00373-023-02660-w

M3 - Article

VL - 39

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 4

M1 - 65

ER -