The phylogenetic rank of a graph
Abstract
The Pachter-Sturmfels phylogenetic rank of a graph G is the minimal number of metric trees needed to embed G isometrically. Here, all edges of G are of length one and the product of metric trees is endowed with the supremum norm. We develop both a greedy and an exact algorithm for computing phylogenetic ranks. Using our algorithms, we construct a database of phylogenetic ranks which includes all graphs on 6 and 7 vertices. In particular, we exhibit examples disproving that the phylogenetic rank is hereditary, bounded by ⌈ n/2 ⌉, and a generalised 4-point conjecture by Pachter and Sturmfels. In addition, we show that the phylogenetic rank is subadditive under 1-sums and certain 2-vertex-sums, and that it is trivially upper bounded by n-1, where n denotes the number of vertices. We also provide a complete classification of graphs with phylogenetic rank 1 and construct several infinite families with phylogenetic rank ⌈ n/2 ⌉.
Related
- Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs
- Mixed partition functions are exactly the graph parameters of exponentially bounded edge-connection rank
- The prime spectrum of the talented monoid of a higher-rank graph and applications
- Asymptotic Rank of Complete Graph Tensors
- Remarks on the Farthing--Muhly--Yeend inverse semigroup of a finitely aligned higher-rank graph
BibTeX
@misc{ashworth2026phylogenetic,
title = {{The phylogenetic rank of a graph}},
author = {Franklin Ashworth and Oliver Clarke and Jeffrey Giansiracusa and Jackson Jones and Julio Quijas-Aceves and Yue Ren},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19372},
eprint = {2609.19372},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19372},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The phylogenetic rank of a graph
AU - Franklin Ashworth
AU - Oliver Clarke
AU - Jeffrey Giansiracusa
AU - Jackson Jones
AU - Julio Quijas-Aceves
AU - Yue Ren
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19372
UR - https://arxiv.org/abs/2609.19372
AB - The Pachter-Sturmfels phylogenetic rank of a graph G is the minimal number of metric trees needed to embed G isometrically. Here, all edges of G are of length one and the product of metric trees is endowed with the supremum norm. We develop both a greedy and an exact algorithm for computing phylogenetic ranks. Using our algorithms, we construct a database of phylogenetic ranks which includes all graphs on 6 and 7 vertices. In particular, we exhibit examples disproving that the phylogenetic rank is hereditary, bounded by ⌈ n/2 ⌉, and a generalised 4-point conjecture by Pachter and Sturmfels. In addition, we show that the phylogenetic rank is subadditive under 1-sums and certain 2-vertex-sums, and that it is trivially upper bounded by n-1, where n denotes the number of vertices. We also provide a complete classification of graphs with phylogenetic rank 1 and construct several infinite families with phylogenetic rank ⌈ n/2 ⌉.
ER -