Injective split systems

DOI10.1007/S00373-023-02660-WMaRDI QIDQ6115433zbMATH OpenWikidataFDO

Authors Marc Hellmuth, Katharina T. Huber, Vincent Moulton, G. E. Scholz, Peter F. Stadler

Publication date 12 July 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Buneman graphmedian graphsplit system

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (05C99)

Abstract: A split system $mathcalS$ 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$, $xinX$. To any such split system $mathcalS$ we can associate the Buneman graph $mathcalB(mathcalS)$ which is essentially a median graph with leaf-set $X$ that displays the splits in $mathcalS$. In this paper, we consider properties of injective split systems, that is, split systems $mathcalS$ with the property that $mathrm{med}_{mathcalB(mathcalS)}(Y)eqmathrm{med}_{mathrmB(mathcalS)}(Y^{\prime })$ for any 3-subsets $Y,Y^{\prime }$ in $X$, where $mathrm{med}_{mathcalB(mathcalS)}(Y)$ denotes the median in $mathcalB(mathcalS)$ of the three elements in $Y$ considered as leaves in $mathcalB(mathcalS)$. 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 $mathcalB(mathcalS)$ needs to become in order for a split system $mathcalS$ 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.

Recommendations

• Counting vertices and cubes in median graphs of circular split systems
• On the number of vertices and edges of the Buneman graph
• Some variations on a theme by Buneman
• Linearly independent split systems
• Blocks and cut vertices of the Buneman graph

Cites work

• A canonical decomposition theory for metrics on a finite set
• Basic phylogenetic combinatorics.
• Blocks and cut vertices of the Buneman graph
• Counting vertices and cubes in median graphs of circular split systems
• From copair hypergraphs to median graphs with latent vertices
• From modular decomposition trees to rooted median graphs
• scientific article; zbMATH DE number 3974977 (Why is no real title available?)
• scientific article; zbMATH DE number 3769710 (Why is no real title available?)
• scientific article; zbMATH DE number 53860 (Why is no real title available?)
• scientific article; zbMATH DE number 1339499 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• On the number of vertices and edges of the Buneman graph
• Orthology relations, symbolic ultrametrics, and cographs
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• The median stabilization degree of a median algebra
• The structure of median graphs
• Three-way symbolic tree-maps and ultrametrics

Cited in

(7)

• Injectivity and weak ternary separation
• Counting vertices and cubes in median graphs of circular split systems
• Blocks and cut vertices of the Buneman graph
• Phylogenetic analysis, split systems and Boolean functions
• Arboreal networks and their underlying trees
• Can you tell a tree from its branches?
• On a generalization of median graphs: k-median graphs

This page was built for publication: Injective split systems

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