Order distances and split systems

Vincent Moulton, Andreas Spillner

Research output: Contribution to journalArticlepeer-review

5 Downloads (Pure)

Abstract

Given a pairwise distance D on the elements in a finite set X, the order distanceΔ(D) on X is defined by first associating a total preorder ≼ x on X to each x ∈X based on D, and then quantifying the pairwise disagreement between these total preorders. The order distance can be useful in relational analyses because using Δ(D) instead of D may make such analyses less sensitive to small variations in D. Relatively little is known about properties of Δ(D) for general distances D. Indeed, nearly all previous work has focused on understanding the order distance of a treelike distance, that is, a distance that arises as the shortest path distances in a tree with non-negative edge weights and X mapped into its vertex set. In this paper we study the order distance Δ(D) for distances D that can be decomposed into sums of simpler distances called split-distances. Such distances D generalize treelike distances, and have applications in areas such as classification theory and phylogenetics.

Original languageEnglish
Pages (from-to)291–308
Number of pages18
JournalOrder
Volume39
Issue number2
Early online date20 Sep 2021
DOIs
Publication statusPublished - Jul 2022

Keywords

  • Circular split system
  • Flat split system
  • Kalmanson distance
  • Order distance
  • Total preorder
  • Treelike distance

Cite this