ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 14 (2018) 117-128
https://doi.org/10.26493/1855-3974.831.e12
(Also available at http://amc-journal.eu)
Axiomatic characterization of transit functions
of hierarchies
Manoj Changat, Ferdoos Hossein Nezhad
Department of Futures Studies, University of Kerala, Thiruvananthapuram - 695 581, India
Peter F. Stadler *
Bioinformatics, Department of Computer Science, Härtelstraße 16-18, D-04107 Leipzig, Germany
Received 3 April 2015, accepted 2 May 2017, published online 22 June 2017
Transit functions provide a unifying approach to many results on intervals, convexities, and betweenness. Here we show that hierarchical structures arising in cluster analysis and phylogenetics have a natural characterization in terms of transit functions and that hierarchies are identified by multiple combinations of independent axioms.
Keywords: Transit functions, convexities, hierarchies, rooted trees, axiom systems. Math. Subj. Class.: 05C05, 05C99, 52A01
1 Introduction
Rooted trees are commonly used in phylogeny to represent the evolutionary history of a collection of organisms. Internal vertices in these trees are interpreted as the last common ancestors for their extant descendants, which are represented by the leaves of the tree. Phylogenetic trees not only depict an evolutionary history, they also express a hierarchical classification of the organisms by identifying subtrees with taxonomic groups such as animals, plants, or insects. The tree structure of evolution thus implies a hierarchical classification of life forms. A wide variety of methods has become available in computational
*PFS holds additional affiliations with the Max Planck Institute for Mathematics in the Sciences in Leipzig, the Fraunhofer Institute for Cell Therapy and Immunology in Leipzig, the Institute for Theoretical Chemistry at the University of Vienna, the Center for noncoding RNA in Health and Technology in Kopenhagen University, and the Santa Fe Institute.
E-mail address: mchangat@gmail.com (Manoj Changat), ferdows.h.n@gmail.com (Ferdoos Hossein Nezhad)studla@bioinf.uni-leipzig.de (Peter F. Stadler)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
118
Ars Math. Contemp. 14 (2018) 117-128
biology to infer phylogenetic trees from diverse sources of data [12], most prominently among them DNA sequences. Hierarchical clustering produces an analogous tree structure without the need to pre-suppose an evolutionary process in time that gives rise to the clusters. Instead, these intrinsic (dis)similarities of the objects under considerations are used to obtain a hierarchical classification [1]. Clustering is a topic of key importance in data mining and knowledge discovery.
Throughout this contribution, V is a finite, non-empty set. We use the notation c to mean proper subset, and write C otherwise.
Definition 1.1. A hierarchy on V is a set system C G 2V so that
(H1) V G C,
(H2) {x} G C for all x G V.
(H3) A, B G C implies that either A n B = 0, A = B, A c B, or B c A.
Hierarchies have a representation as a rooted tree T with leaf set V. Denote by VU W the complete vertex set of T, i.e., W is the set of internal vertices of T including the root denoted by r. For simplicity we disregard the trivial case of T consisting of a single vertex. Furthermore, we require that every internal vertex has at least two children. This type of tree is sometimes called homeomorphically irreducible. Hence we assume from |V| > 2. There is a natural partial order < on V U W so that x < y if and only if y lies on the path from x to the root r. The leaves are minimal elements with respect to the root is the unique maximal element. For any subset A C V U W of vertices in T, the intersection of the paths from v G A to the root is again a path. The minimal vertex in this path is the last common ancestor of A, denoted by lca(A). For each vertex x G V U W, the subtree T [x] below x consists of all vertices y ^ x, i.e , all those for which the path to the root passes through x. For its leaf set we write V[x] = V[T[x]] = {y G V|y ^ x}. Clearly we have lca(V[x]) = x for all x G V U W, and V[x] = {x} if and only if x G V. Moreover, V [r] = V.
There is a well-known bijection between hierarchies and homeomorphically irreducible rooted trees. Given C, the tree TC represents the elements of C as vertices so that V becomes the root, the singleton sets {x}, x g V become the leaves, and each internal vertex u of TC corresponds to a non-trivial cluster which then can be represented as V [T [u]] G C. There is an edge between u and u' if and only if V[T[u]] = V[T[u']] and there is no u" so that V[T[u]] c V[T[u'']] c V[T[u']] or V[T[u']] c V[T[u'']] c V[T[u]]. The tree Tc is therefore (isomorphic to) the Hasse diagram of C w.r.t. set inclusion. Conversely, consider an internal vertex u G W. The leaf ui,..., uk of u, define a partition of V[T[u]], since the leaf sets of the subtrees are disjoint, non-empty, and satisfy V[T[u]] = |Ji V[T[u^]. Thus T defines a unique hierarchy TC.
With a hierarchy C we can naturally associate the function RC : V x V ^ 2V, defined
by
Rc(x,y) = f|{A G C|x, y G A}	(1.1)
as the intersection of all clusters that simultaneously contain both x and y. It follows immediately from property (H3) that RC(x, y) is itself a cluster of C, i.e., RC (x, y) G C for all x, y G V. With a homeomorphically irreducible rooted tree T we can, in an equally natural way, associate a function RT : V x V ^ 2V on the leaves of T by setting
Rt(x, y) = V[lca({x, y})]
(1.2)
M. Changat et al.: Axiomatic characterization of transit functions of hierarchies
119
By construction RT (x, y) consists of all the leaves of the subtree "spanned" by x and y. The bijection of trees and cluster systems, and the fact that V[lca({x, y})] G CT furthermore, implies that RT = RCt and, conversely, RC = RTc .
Function R : V x V ^ 2V have been studied extensively under the name transit functions [9]. In graph theory, they arise in a broad range of contexts involving betweenness, intervals, and convexity [2, 3, 4, 6, 8, 5, 7, 9, 10, 11]. A topic of particular interest in this field is the characterization of graph classes in terms of first order properties of their transit functions and the axiomatic characterization of a well-known transit function in terms of (transit) axioms. Therefore we ask in this contribution whether there is a set of axioms that uniquely determines the transit functions RT of rooted trees.
Formally, a transit function on a non-empty set V is a function R : V x V ^ 2V satisfying the three axioms
(t1) u G R(u, v) for all u, v G V. (t2) R(u, v) = R(v, u) for all u, v G V. (t3) R(u, u) = {u} for all u G V.
Basically, a transit function describe how one can move from an element u to an element v through elements in R(u, v).
A convexity K c 2V is closed under intersections and both V G K and 0 G K. In the context of transit function, we are primarily interested in convexities that in addition satisfy {x} G K for all x G V .A hierarchy is, therefore, a particular kind of convexity (to be precise, we have to add the empty set to the hierarchy C as defined by (H1), (H2), and (H3) to guarantee closure under intersections). The converse is not true, however, as exemplified by K = {{a, b}, {b, c}, {6}, 0}.
The canonical transit function of a convexity K is given by the convex hulls spanned by x and y, i.e., it is defined by equ.(1.1) [9]. For every transit function R on V, there is an associated convexity, where a subset W of V is R-convex if R(u, v) C W, for every u, v G W. The family of RT-convex sets coincide with the hierarchic convexity on V.
The following non-trivial betweenness axioms were considered already by Mulder [9]:
(61)	x G R(u, v), x = v ^ v G R(u, x);
(62)	x G R(u,v) ^ R(u, x) C R(u,v); (m) x, y G R(u, v) ^ R(x, y) C R(u, v).
A transit function R is called monotone if it satisfies axiom (m). It is satisfied by construction for the canonical transit function of a convexity, see e.g. [4, 9], and thus in particular by transit function of a hierarchy.
2 Transit functions of hierarchies
In the context of transit functions of hierarchies (or rooted trees) we encounter several additional betweenness properties:
(a) For all u G V, there is u so that R(u, u) = V. (h) R(u, v) n R(x, y) = 0 ^ R(u, v) C R(x, y) or R(x, y) C R(u, v). (h') x G R(u, v) ^ R(u, x) = R(u, v) or R(x, v) = R(u, v).
120
Ars Math. Contemp. 14 (2018) 117-128
(h'') x € R(u, v) ^ R(u, v) = R(u, x) U R(x, v). (h''') x € R(u,v) ^ R(u, x) = R(x,v).
(m') R(u, v) n R(x, y) = 0 ^ 3p and q such that R(u, v) n R(x, y) = R(p, q)
We say that a transit function is hierarchical if it satisfies axiom (h).
Now consider a hierarchy C and its transit function R = RC defined in equ.(1.1). We easily check that (m) is satisfied also without recourse to the theory of convexities: Since R(u, v) € C it follows immediately that for all x, y € R(u, v) the smallest element of C that contains both x and y must be a subset of R(u, v). Thus R(x, y) C R(u, v). Hence R satisfies the axioms (m) and thus also (62).
On the other hand, RC does not satisfy (61), i.e., it is not a betweenness in the sense of Mulder [9]:
Example 2.1. Set V = {a, 6, c, d}, R(a, 6) = R(a, c) = R(6, c) = V - {d}, and R(a, d) = R(6, d) = R(c, d) = V. It corresponds to the hierarchy {{{a}, {6}, {c}}, {d}}. Since 6 € R(a, c) and c € R(a, 6), (61) does not hold.
Axiom (h) simply states that the transit sets form a hierarchy, which is obviously true by virtue of the defining equ.(1.1) for the transit function of any hierarchy. Axiom (m') states that the system of transit sets is closed under intersections. Property (m') is, in fact, an immediate consequence of (h) since either R(u, v) n R(x, y) = 0 in this case implies R(p, q) = R(u, v) or R(p, q) = R(x, y). The canonical transit function of a convexity, and thus RC, therefore satisfies (m').
Theorem 2.2. The collection of transit sets of a transit function R is a hierarchy, i.e., a convexity satisfying (H3), if and only if R satisfies (m), (m'), and there is a pair p, q € V so that R(p, q) = V.
Proof. By construction, the canonical transit function of a convexity fulfills the three conditions. Conversely, it is well known that the transit sets are convex (w.r.t. to R) if and only if R satisfies (m). Condition (m') is necessary and sufficient to ensure that the intersection of transit sets is closed under intersection, and the existence of a pair p, q € V so that
R(p, q) = V is equivalent to V € K.	□
Axiom (h') is motivated by the following simple observation for rooted trees: Let u and v be two leaves of a rooted tree T. Consider an arbitrary leaf x € V[T[lca(u, v)]]. Then one of the three statements is true: (i) x is contained in the same subtree rooted by a child of lca(u, v) as v, (ii) x is contained in the same subtree rooted by a child of lca(u, v) as u, (iii) x is located in a subtree that is rooted at a child of lca(u, v) that contains neither u nor v. In the first case lca(x, v) = lca(u, v), in the second case lca(x, u) = lca(u, v), and in the third case lca(u, x) = lca(v,x) = lca(u,v). Thus, V[T[lca(u, v)]] coincides with V[T[lca(u, x)]] or V[T[lca(u, y)]].
In the following, we derive the analogous result for hierarchies without making use of the corresponding rooted tree.
Lemma 2.3. Let C be a hierarchy of a finite set V. The associated transit function R = RC defined in equ.(1.1) satisfies (h').
Proof. Let u, v, x € V and x € R(u, v). The statement of (h') holds trivially if x = u or
x = v. If u = v then R(u, v) = {u} by (t3) and thus x = u.
M. Changat et al.: Axiomatic characterization of transit functions of hierarchies
121
Thus, we assume that u, v and x are pairwise distinct. Define W [u|v] as the largest cluster i.e., W[u|v] G C, so that u G W[u|v] and v G W[u|v]. By (H1) and (H3) we have {u} C W[u|v] C R(u, v), hence W[u|v] is well defined.
Suppose q G W[u|v]. Then W[q|v] n W[u|v] = 0 and hence W[q|v] C W[u|v]. By construction, W [q|v] is the largest cluster in C that contains q but not v. Since W [u|v] also has this property, we have W[u|v] C W[q|v], i.e., W[q|v] = W[u|v] for all q G W[u|v].
Let p G W[u|v] and q G W[v|u]. Since W[u|v] = W[p|v], W[v|u] = W[q|u], and R(p,q) are clusters of C, W[p|v] n R(p,q) = 0 and W[q|u] n R(p,q) = 0, (H3) implies W[p|v] C R(p, q) and W[q|u] C R(p, q). Since R satisfies (m) we have R(p, q) C R(u, v) since p, q G R(u, v). On the other hand, u, v G R(p, q) and R(u, v) is by construction the smallest cluster that contains both u and v so that R(u, v) C R(p, q). Thus
R(p,q) = R(u, v).
In particular, if x G W[u|v] then R(x, v) = R(u, v).
Now suppose x G R(u, v) \ (W[u|v] U W[v|u]). Using (H3) again we conclude W[u|v] U {x} C R(q, x) for all q G W[u|v] and R(q, x) C R(u, v).
By maximality of W[u|v], W[u|v] U {x} is not contained in any cluster of C that is a (proper) subset of R(u, v) and does not contain v. Hence the smallest cluster containing
W[u|v] U{x}, i.e., R(u, x) also contains v and hence R(u, v). By (m), R(u, x) C R(u, v). Thus R(u, x) = R(v, x) = R(u, v). Thus (h') holds.	□
The hierarchy axiom (H1) implies immediately that there is a pair of points p, q so that R(p, q) = V. For any x G V we have R(x,p) = V or R(x, q) = V, thus the transit function of a hierarchy satisfies axiom (a).
We shall see below that the transit functions of hierarchies also satisfy (h'') and (h'''). Instead of giving direct proofs, we will draw these conclusions directly from general implications between the above properties of transit functions.
3 Characterization
Theorem 3.1. Suppose R satisfies (a), (h'), (h), and (m). Then R is the transit function of a hierarchy C as defined in equ.(1.1).
Proof. It follows immediately from (h), (a), and (t3) that CR = {R(p, q)|p, q G V} is a hierarchy. The corresponding transit function Q := RCr can be represented as
Q(u, v) = p| {R(p, q), p, q G V|u, v G R(p, q)}	(3.1)
Thus R is the transit function of the hierarchy C if and only if R = Q. By (t1) and (m) we have Q(u, v) C R(p, q) for all p, q so that u, v G R(p, q). In particular, therefore Q(u, v) C R(u, v). The smallest transit set R(p, q) that contains both u and v (which is well-defined by virtue of the hierarchy axioms) there is contained in R(u, v).
We now construct a partition A of R(u,v) as follows: (i) Au := {x G R(u, v)| R(x,u) = R(u,v)} and Av := {x G R(u, v)|R(x, v) = R(u, v)}. By (h') we have R(x,v) = R(u, v) for x G Au and R(x,u) = R(u,v) for x G Av. (ii) The remainder R' = R(u,v) \ (Au U Av) consists, by axiom (h') of all x G R(u, v) that satisfy R(u, x) = R(v, x) = R(u, v). If R' is nonempty, choose an arbitrary q G R' and define Aq := {x G R(u, q)|R(q, x) C R(u, x)} and note that, by (h'), R(q, u) = R(u,x) = R(u, v). Since R(u, x) = R(v, x) = R(v, q) we Aq = {x G R(v, q)|R(q, x) C R(v, x)}
122
Ars Math. Contemp. 14 (2018) 117-128
as alternative representation. (iii) Now replace R' ^ R \ Aq, pick a point q' in R' and construct Aqi = {x G R(u,q')IR(q' ,x) c R(u,x)}. Again, we have R(u,q') = R(u,q) = R(u, v), and we can replace u by v or q in the definition of Aq>. We repeat this construction until R' is empty and arrive at the A := {Au, Av,Aq,... } of R(u, v).
By construction, A has the property that R(p, q) C R(u, v) if and only if p,q G Az for some Az g A and R(x, y) = R(u, v) if and only if x and y are contained in two different classes of A.
Suppose p,q G Az and there is w g R(p, q) so that w / Az. By (m) R(p, w) C R(p, q) and by construction of Az we have R(p, q) c R(u, v). On the other hand, w / Az implies, for all p G Az, that R(p, w) = R(u, v), leading to the contradiction R(p, q) c R(p, w). Thus p,q G Az implies R(p, q) C Az.
If Az = R(p, q), then there is s g Az \ R(p, q). We have R(p, s) n R(p, q) = 0, thus by (h) R(p, q) c R(p, s). Repeating the argument we eventually arrive at ap G Az so that R(p,p) = Az, i.e., Az gC.
Since u and v are contained in two different classes of A, and R(p, q) C Az whenever p,q G Az we can reason as follows: If p,q G R(u, v) and u,v G R(p, q) then p and q are contained in different classes of A and therefore R(p, q) = R(u, v). The smallest transit set that contains u, v therefore is R(u, v). It follows that R(u, v) = Q(u,v).	□
As a by-product of the proof, we have obtained, for each transit set R(u, v), its partition into maximal proper subsets R(p, q). This amounts to an explicit construction of the Hasse diagram of C directly from the transit function.
4 Implications among axioms
The characterization in Theorem 3.1 can be simplified further by observing that the conditions (a), (h'), (h), and (m) are not independent. First, find that we can simply drop (a) by virtue of (h) ^ (a).
Lemma 4.1. Let R be a transit function on V satisfying axiom (h). Then R satisfies axiom
(a).
Proof. For u,v G V consider a vi G V so that R(u, v) n R(u, vi) = 0. Since (h) holds, we have R(u, v) C R(u, vi) or R(u, vi) C R(u, v). W.l.o.g. assume R(u, v) C R(u, vi). If R(u,vi) = V there is nothing to show. Otherwise, choose vj G V such that vj G R(u, vi). Again, we have R(u, vi) n R(u, vj) = 0 and thus, by (h), R(u, vi) C R(u, vj) or R(u,vj) C R(u,vi). Since vj G R(u,vi) we can rule out R(u,vj) C R(u,vi) and conclude that R(u, vi) C R(u, vj). Repeating this argument we obtain a chain R(u, v) C R(u, vi) C R(u, vj) C ... C R(u, vk) of sets that, in each iteration increase by at least one element. Thus R(u, vk) = V for some k not larger than IV|, and vk is desired element u so that R(u, u) = V.	□
Several, but not all pairs of the axioms (m), (m'), (h), (h'), (h''') are equivalent and characterize the transit functions of hierarchies:
Lemma 4.2. Let R be a transit function satisfying axioms (h) and (m) on V. Then R satisfies axiom (h').
Proof. Suppose (h) and (m) holds. For all u,v G V and all x G R(u,v) we have R(u, x) C R(u, v) and R(x, v) C R(u, v) because of (m). By (h) we have R(u, x) C
M. Changat et al.: Axiomatic characterization of transit functions of hierarchies
123
R(x, v) or R(x, v) C R(u, x), R(u, x) C R(u, v) or R(u, v) C R(u, x), and R(x, v) C R(u,v) or R(u,v) C R(x,v). If R(u,x) C R(x,v), thus {x,v,u} G R(x,v) and by (m) R(u,v) C R(x,v). If R(x,v) C R(u, x), we have {x,v,u} C R(u,x) and thus R(u,v) C R(u,x). If (h') does not hold, there are u,v,x G V can be chosen so that neither R(u, v) C R(u, x) nor R(u, v) C R(x, v), a contradiction.	□
Lemma 4.3. Let R be a transit function satisfying axioms (h) and (h') on V. Then R satisfies axiom (m).
Proof. Let u,v G V and x,y G R(u,v). From (h) we obtain that R(u,v) C R(x,y) or R(x,y) C R(u,v). In second case we are, done. Thus suppose R(x,y) ^ R(u,v), i.e., R(u,v) c R(x,y), and in particular u,v G R(x,y). From (h') we known that at least one of R(u, x) and R(v, x), and at least one of R(u, y) and R(v, y) equals R(u, v). Since u,v G R(x,y), (h') implies R(u,x) = R(x,y) or R(u,y) = R(x,y) as well as R(x,v) = R(x,y) or R(v,y) = R(x,y). In total, this leaves 16 cases, of which all but two directly lead to the contradiction R(u, v) = R(x, y). In case (i), R(u, x) = R(v,y) = R(u,v) and R(u,y) = R(v,x) = R(x,y). Here, y G R(u,x) and (h') implies R(u, y) = R(u, x) or R(y, x) = R(u, x), which further yields the contradiction R(x, y) = R(u, y) = R(u, x) = R(u, v). In case (ii) R(u, x) = R(v, y) = R(x, y) and R(u,y) = R(v,x) = R(u,v). Here, x G R(u,y) and (h') implies R(u,x) = R(u,v) or R(x, y) = R(u, v), which leads to an analogous contradiction.	□
Lemma 4.4. Let R be a transit function satisfying axioms (h) and (b2) on V. Then R satisfies axiom (m).
Proof. Suppose x,y G R(u, v). By (b2) R(u, x) C R(u, v) and R(u, y) C R(u, v). Since u G R(u,x) n R(u,y), (h) implies that R(u,x) C R(u,y) or R(u,y) C R(u,x). In the first case, x g R(u,y) and thus R(x,y) C R(u,y) C R(u,v). In the second case y G R(u, x) and hence R(x, y) C R(u, x) C R(u, y), i.e., (m) holds.	□
Lemma 4.5. Let R be a transit function satisfying axioms (h) and (m) on V. Then R satisfies axiom (h''').
Proof. Suppose z G R(u,v). By (h) R(u,v) c R(u, z) and R(u,v) c R(v,z), and further R(u, z) C R(v, z) or R(v, z) C R(u, z). In either case, {u, v, z} C R(u, z) and {u, v, z} C R(v, z), hence by (m) R(u, z) C R(v, z) and R(v, z) C R(u, z). Thus (h''') holds.	□
Lemma 4.6. Let R be a transit function satisfying axioms (h''') and (m) on V. Then R satisfies axiom (h).
Proof. Suppose (h''') and (m) but (h) does not, i.e., there is u,v,x,y G V such that R(x, y) n R(u, v) = 0 but neither R(x, y) ^ R(u, v) nor R(u, v) ^ R(x, y). Thus there is w G R(x, y) n R(u, v), a G R(u, v) such that a G R(x, y) and b G R(x, y) such that b G R(u,v). Furthermore, a, b, and w are pairwise disjoint. As a consequence of (m) we have R(a,u) C R(u,v), R(a,v) C R(u,v), R(a,w) C R(u,v), R(b,x) C R(x,y), R(b,y) C R(x,y), and R(b,w) C R(x,y). Since a G R(x,y) and hence a G R(b,y) and a G R(b,w), (h''') implies R(a,y) = R(a,x) = R(a,b) = R(a,w). Analogously, b G R(u,v) implies R(u,b) = R(b,v) = R(a,b) = R(b,w). In particular, therefore, R(a, w) = R(b, w). Thus b G R(a, w) C R(u, v) and a G R(b, w) C R(x, y), contradicting the definition of a and b. Thus (h) holds.	□
124
Ars Math. Contemp. 14 (2018) 117-128
Lemma 4.7. Let R be a transit function satisfying axioms (h') and (h''') on V. Then R satisfies axiom (m).
Proof. Let x, y G R(u, v) and suppose (m) does not hold, i.e., there is z G R(x, y) such that z G R(u, v). By (h''') we have R(u, z) = R(v, z). Using (h') x G R(u, v) implies R(u, x) = R(u, v) or R(x, v) = R(u, v), and y G R(u, v) implies R(u, y) = R(u, v) or R(v, y) = R(u, v). z G R(x, y) implies R(x, z) = R(x, y) or R(z, y) = R(x, y). Thus z is not contained R(u, x) or R(x, v), and it is not contained in R(u, y) or R(v, y). Using (h''') again, therefore R(u, z) = R(x, z) or R(x, z) = R(z, v). Since R(u, z) = R(v, z), we have R(u, z) = R(v, z) = R(x, z). Analogously, z is not contained in R(u, y) or R(v,y), and thus (h''') implies R(u, z) = R(z, y) or R(v, z) = R(z, y), and further R(u, z) = R(v, z) = R(y, z). Collecting all equalities we arrive at R(u, z) = R(v, z) = R(x, z) = R(y, z) = R(x, y). Therefore u G R(x, y) and (h') implies R(u, x) = R(x, y) or R(u, y) = R(x,y).
In the first case R(u, x) = R(x, y) = R(u, v) and (h') implies R(x,v) = R(u, v), whence R(x, v) = R(x, y) and finally R(v,y) = R(x, y). Thus y G R(x,v), and (h') implies R(x, y) = R(x,v) or R(y, v) = R(x,v), i.e., R(x,y) = R(x, v) = R(u,v), a contradiction.
In the second case R(u, y) = R(x, y) = R(u, v) and (h') implies R(v, y) = R(u, v), whence R(v,y) = R(x, y) and finally R(v, x) = R(x, y). Thus x G R(v, y), and (h') implies R(x, y) = R(v, y) or R(x, v) = R(v, y), i.e., R(x, y) = R(v, y) = R(u, v), again a contradiction. Thus R(x, y) C R(u, v).	□
Lemma 4.8. Let R be a transit function satisfying axioms (h') and (62) on V. Then R satisfies axioms (h'') and (m).
Proof. Let x G R(u, v). Because of (h') we have R(u, v) = R(u,x) or R(u, v) = R(x,v). Condition (62) establishes that R(u, x) C R(u,v) and R(x,v) C R(u, v), and thus R(u,x) U R(v, x) = R(u, v), i.e., (h'') holds. Thus, for all y G R(u, v) we have y G R(u, x) or y G R(x, v). W.l.o.g., y G R(x, v). By (h''), R(x, v) = R(x, y) U R(y, v), hence R(x,y) C R(u, v).	□
Lemma 4.9. Let R be a transit function satisfying axioms (h''') and (62) on V. Then R satisfies axiom (m).
Proof. Let x, y G R(u,v). Suppose R(x, y) ^ R(u, v) which implies that y G R(u, x), otherwise by (62) R(x, y) C R(u, x) C R(u, v), a contradiction. Also as y G R(u, x) thus by (h''') we have R(u, y) = R(x, y) which is again a contradiction as R(u, y) C R(u, v) by (62).	□
5 Independence of axioms
The following examples show that (m), (m'), (h), (h'), (h'') and (h''') are pairwise independent axioms.
Example5.1. (m) ^ (h).
Set V = {a, 6, c, d, f}, R(a, 6) = {a, 6, c}, R(d, f) = {d, f, c} and R(x, y) = {x, y} for all other distinct pairs of points. This transit function satisfies (m) but violates (h): we R(a, 6) n R(d, f) = 0 but both R(a, 6) \ R(d, f) = {a, 6} and R(d, f) \ R(a, 6) = {d, f} are non-empty.
M. Changat et al.: Axiomatic characterization of transit functions of hierarchies
125
Example 5.2. (m) ^ (h'); (m) ^ (h'''); and (m) ^ (h'').
Let V = {u, v, x, y}, R(u, v) = V, and R(p, q) = {p, q} for all other pairs of distinct points. It satisfies (m) but violates (h'). Axiom (h'') does not hold because R(u, v) = R(u,x) U R(x,v). Axiom (h''') is violated by u G R(x, y) = {x, y} and R(u,x) = {u, x} = {u, y} = R(u, y).
As a consequence, the weaker conditions (62) of course also fails to imply (h), (h'),
(h''), or (h''').
Example 5.3. (h) ^ (m); (h) ^ (h'); (m') ^ (m); (m') ^ (h'). Let V = {u, v, x, y, a} and consider the transit function R defined by R(u, v) = V - {a} and R(x, y ) = V for all other distinct pairs x, y G V. This transit function satisfies ( h) and (m'). However, we have x, y G R(u, v) but R(x, y) ^ R(u, v) contradicting (m). R also violates (h'), since x G R(u, v), but neither R(u, x) = R(u, v), nor R(x, v) = R(u, v).
Example 5.4. (h) ^ (h''').
Set V = {a, 6, c, d}, R(a, 6)	= {a, 6}, R(a, c) = {a, 6, c}, and R(x,y) = V for all
other distinct pairs x, y G V.	(h) holds, but (h''') does not hold since c G R(a, 6) but
R(a, c) = R(6, c).
Example 5.5. (h') ^ (m).
Set V = {a, 6, c, d}, R(a, 6) = R(a, d) = {a, 6, d}, R(a, c) = R(6, c) = {a, 6, c}, and R(6, d) = R(c, d) = {6, c, d}. Here (h') holds, but not (62) and hence not (m).
Example 5.6. (h') ^ (h); (h') ^ (h''').
Set V = {a, 6, c, d} and R(x, y) = {x, y} for all x, y G V. Axiom (h') is trivially satisfied. Since the transit sets do not form a hierarchy, (h) does not hold. Furthermore, c G R(a, 6) and R(a, c) = {a, c} = {6, c} = R(6, c), i.e., (h''') does not hold.
Example 5.7. (h''') ^ (m).
Set V = {a, 6, c, d}, R(a, 6) = R(a, c) = {a, 6, c}, and R(x, y) = V for all other distinct pairs x, y G V. (h''') holds but (m) does not hold since {6, c} G R(a, 6) = R(a, c) but R(6, c) £ R(a, c) = R(a, 6).
Example 5.8. (h''') ^ (h).
Set V = {a, 6, c, d}, R(a, 6) = R(6, c) = {a, 6, c}, R(a, c) = {a, c, d}, and R(a, d) = R(6, d) = R(c, d) = V. (h''') holds, but (h) is violated because R(a, 6) ^ R(a, c) and R(a, c) ^ R(a, 6). Furthermore, (h') does not hold since d G R(a, c) but R(a, d) = {a, d} = R(a, c) and R(c, d) = R(a, c).
Example 5.9. (m) ^ (m').
Set V = {a, 6, c, d, e, f, g}, R(a, 6) = {a, 6, c, d, e}, R(f, g) = {c, d, e, f, g}, and R(x, y) = {x, y} for any other pair x, y G V. Clearly R is monotone. Here R(a, 6) n R(f, g) = {c, d, e}, which is convex, but there is no p, q G X such that {c, d, e} = R(p, q), i.e., (m') does not hold.
Example 5.10. (h') ^ (62); (h') ^ (h''').
Set V = {a, 6, c, d}, R(a, 6) = R(6, c) = {a, 6, c}, R(a, c) = R(c, d) = {a, c, d} and R(a, d) = R(6, d) = {a, 6, d}. (h') holds but nor (62) and (h'''), since c G R(a, 6) but R(a,c) ^ R(a, 6), i.e., (62) does not hold. Since d G R(6, c) but R(6, d) = R(c, d) implies that (h''') does not hold.
126
Ars Math. Contemp. 14 (2018) 117-128
Example 5.11. (h'") & (h); (h'") & (b2); (h'") & (h').
Set V = {a, b, c, d}, R(a, b) = R(b, c) = {a, b, c} ,R(a, c) = {a, c, d} and R(a, d) = R(b, d) = R(c, d) = V. (h''') holds for R. Since R(a, b) £ R(a, c) and R(a, c) £ R(a, b), thus (h) does not hold. c g R(a, b) but R(a, c) £ R(a, b) hence (b2) does not hold. As d G R(a, c) but R(a, d) = R(a, c) and R(c, d) = R(a, c) thus (h') does not hold for R.
Hence (b2), (h') and (h''') are independent axioms. While we have seen above that, some pairs of axioms are sufficient to characterize transit functions of hierarchies, this is not the case for all pairs.
Example 5.12. (h') and (m) & (h).
Set V = {a, b, c, d}, R(a, b) = {a, b}, R(a, c) = R(b, c) = {a, b, c}, R(a, d) = {a, d}, R(b, d) = {b, d} and R(c, d) = {c, d}. Clearly, both (h') and (m) are satisfied. However, R(a, d) n R(b, d) = 0, and neither transit set is contained in the other, hence (h) does not hold.
Example 5.13. (h) and (h''') & (m).
Set V = {a, b, c, d}, R(a, b) = R(a, c) = {a, b, c} and R(x, y) = V for all other distinct pair x,y G V. (h''') and (h) hold, but (m) does not hold since {b, c} G R(a, b) = R(a, c) but R(b, c) £ R(a, c) = R(a, b).
Example 5.14. (m) and (m') & (h'').
Set V = {a, b, c, d}, R(a, b) = V, and R(x, y) = {x, y}, for any other distinct elements x,y G V. R satisfies (m) and (m') but does not satisfy (h''), since c g R(a,b) but R(a,b) = R(a,c) U R(c, b).
Example 5.15. (m) and (m') & there is p, q such that R(p, q) = V.
Set V = {a, b, c, d}, R(a, b) = {a, b, c}, R(x, y) = {x, y}, for any other distinct elements
x,y G V. R satisfies (m) and (m') but there does not exist any p, q such that R(p, q) = V.
Example 5.16. (h') and (h'') & (h); (h') and (h'') & (h''').
Set V = {a,b,c,d}, R(a,c) = R(b,c) = {a,b,c}, R(x,y) = {x,y}, for any other distinct elements x,y G V. R satisfies (h') and (h'') but R does not satisfy (h) since
R(b, d) n R(b, c) = 0 but R(b, d) £ R(b, c) and R(b, c) £ R(b, d). Also R does not satisfy (h'''), since d G R(b, c) but R(b, d) = R(d, c) .
Example 5.17. (m) and (m') and (a) & (h).
Set V = {a, b, c, d}, R(a, d) = R(b, d) = R(c, d) = V, R(a, c) = {a, b, c}, R(a, b) = {a, b}, R(b, c) = {b, c} satisfied (m), (m'), and (a) but violates (h) since R(a, b) n R(b,c) = {b}.
Using the results in Section 4 and the examples of non-implications among the axioms (a), (h), (h''), (h'''), (b2), (m), and (m') described in Section 5, we obtain four different sets of axiomatic characterizations of the transit function of a hierarchy as a corollary of Theorem 3.1. This is stated as a Theorem below.
Theorem 5.18. A transit function R on a non-empty set is the transit function of a hierarchy if and only if R satisfies one of the following combinations of two axioms:
1. (h) and (b2),
M. Changat et al.: Axiomatic characterization of transit functions of hierarchies	127
2.	(h'") and (62),
3.	(h) and (h'),
4.	(h') and (h''').
Since each of these four pairs of axioms implies (m), and (m) implies (62), we can also replace (62) by (m) in Thm. 5.18. The implications between axioms and combinations of axioms discussed in this contribution are summarized in Figure 1.
(h A 62 & h'" A 62 & h A h' & h' A h''')
(62)
Figure 1: Summary of implications between axioms. None of the implication arrows is reversible, and only the implications implied by the transitive closure of this diagram hold.
Acknowledgments
We thank Matjaz Kovse for discussions. This work was supported in part by NBHM DAE
under file NBHM/2/48(9)/2014/NBHM (R.P.)/R&D-II/4364 (to MC) and the DFG, Proj.
No. MI439/14-1 (toPFS).
References
[1]	C. C. Aggarwal and C. K. Reddy (eds.), Data Clustering: Algorithms and Applications, Chapman & Hall/CRC Data Mining and Knowledge Discovery Series, CRC Press, 2013.
[2]	J. R. Calder, Some elementary properties of interval convexities, J. London Math. Soc. 3 (1971), 422-428, doi:10.1112/jlms/s2-3.3.422.
[3]	M. Changat, S. KlavZar and H. M. Mulder, The all-paths transit function of a graph, Czechoslovak Math. J. 51 (2001), 439-448, doi:10.1023/a:1013715518448.
[4]	M. Changat and J. Mathew, Induced path transit function, monotone and Peano axioms, Discrete Math. 286 (2004), 185-194, doi:10.1016/j.disc.2004.02.017.
128
Ars Math. Contemp. 14 (2018) 117-128
[5]	M. Changat, J. Mathew and H. M. Mulder, The induced path function, monotonicity and be-tweenness, Discrete Appl. Math. 158 (2010), 426-433, doi:10.1016/j.dam.2009.10.004.
[6]	M. Changat, H. M. Mulder and G. Sierksma, Convexities related to path properties on graphs, Discrete Math. 290 (2005), 117-131, doi:10.1016/j.disc.2003.07.014.
[7]	M. Changat, P. G. Narasimha-Shenoi and I. M. Pelayo, The longest path transit function of a graph and betweenness, Util. Math. 82 (2010), 111-127.
[8]	M. Changat, G. N. Prasanth and J. Mathews, Triangle path transit functions, betweenness and pseudo-modular graphs, Discrete Math. 309 (2009), 1575-1583, doi:10.1016/j.disc.2008.02. 043.
[9]	H. M. Mulder, Transit functions on graphs (and posets), in: M. Changat, S. Klavzar, H. M. Mulder and A. Vijayakumar (eds.), Convexity in Discrete Structures, Ramanujan Mathematical Society, Mysore, volume 5 of Ramanujan Mathematical Society Lecture Notes Series, pp. 117130, 2008, joint proceedings of the International Instructional Workshop held in Thiruvanan-thapuram, March 22 - April 2, 2006 and the International Workshop on Metric and Convex Graph Theory held in Barcelona, June 12- 16, 2006.
[10]	H. M. Mulder and L. Nebesky, Axiomatic characterization of the interval function of a graph, European J. Combin. 30 (2009), 1172-1185, doi:10.1016/j.ejc.2008.09.007.
[11]	L. Nebesky, The induced paths in a connected graph and a ternary relation determined by them, Math. Bohem. 127 (2002), 397-408, http://mb.math.eas.ez/mb12 7-3/5.html.
[12]	C. Semple and M. Steel, Phylogenetics, volume 24 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2003.
[13]	P. F. Stadler and C. R. Stephens, Landscapes and effective fitness, Comments Theor. Biol. 8 (2003), 389-431, doi:10.1080/08948550302439.
[14]	P. F. Stadler and G. P. Wagner, Algebraic theory of recombination spaces, Evol. Comput. 5 (1997), 241-275, doi:10.1162/evco.1997.5.3.241.
[15]	M. L. J. van de Vel, Theory of Convex Structures, volume 50 of North-Holland Mathematical Library, North-Holland Publishing Company, Amsterdam, 1993.
[16]	G. P. Wagner and P. F. Stadler, Complex adaptations and the structure of recombination spaces, in: C. L. Nehaniv and M. Ito (eds.), Algebraic Engineering, World Scientific, pp. 96-115,1999, doi:10.1142/9789814527958, joint proceedings of the Kyoto Workshop on Formal Languages and Computer Systems held in Kyoto, Japan, March 18 - 21, 1997 and the First International Conference on Semigroups and Algebraic Engineering held in Aizu, Japan, March 24 - 28, 1997.
[17]	G. P. Wagner and P. F. Stadler, Quasi-independence, homology and the unity of type: a topological theory of characters, J. Theoret. Biol. 220 (2003), 505-527, doi:10.1006/jtbi.2003.3150.