Shared Ancestry Graphs and Symbolic Arboreal Maps
Katharina T. Huber, Vincent Moulton, Guillaume E. Scholz · SIAM Journal on Discrete Mathematics · 2024
Abstract. A network [Formula: see text] on a finite set [Formula: see text], [Formula: see text], is a connected directed acyclic graph with leaf set [Formula: see text] in which every root in [Formula: see text] has outdegree at least 2 and no vertex in [Formula: see text] has indegree and outdegree equal to 1; [Formula: see text] is arboreal if the underlying unrooted, undirected graph of [Formula: see text] is a tree. Networks are of interest in evolutionary biology since they are used, for example, to represent the evolutionary history of a set [Formula: see text] of species whose ancestors have exchanged genes in the past. For [Formula: see text] some arbitrary set of symbols, [Formula: see text] is a symbolic arboreal map if there exists some arboreal network [Formula: see text] whose vertices with outdegree 2 or more are labeled by elements in [Formula: see text] and so that [Formula: see text], [Formula: see text], is equal to the label of the least common ancestor of [Formula: see text] and [Formula: see text] in [Formula: see text] if this exists, and [Formula: see text] otherwise. Important examples of symbolic arboreal maps include the symbolic ultrametrics, which arise in areas such as game theory, phylogenetics, and cograph theory. In this paper we show that a map [Formula: see text] is a symbolic arboreal map if and only if [Formula: see text] satisfies certain 3- and 4-point conditions and the graph with vertex set [Formula: see text] and edge set consisting of those pairs [Formula: see text] with [Formula: see text] is Ptolemaic (i.e., its shortest path distance satisfies Ptolemy’s inequality). To do this, we introduce and prove a key theorem concerning the shared ancestry graph for a network [Formula: see text] on [Formula: see text], where this is the graph with vertex set [Formula: see text] and edge set consisting of those [Formula: see text] such that [Formula: see text] and [Formula: see text] share a common ancestor in [Formula: see text]. In particular, we show that for any connected graph [Formula: see text] with vertex set [Formula: see text] and edge clique cover [Formula: see text] in which there are no two distinct sets in [Formula: see text] with one a subset of the other, there is some network with [Formula: see text] roots and leaf set [Formula: see text] whose shared ancestry graph is [Formula: see text].