Séminaire Lotharingien de Combinatoire 76 (2016), Article B76a

TREELIKE QUINTET SYSTEMS

SIMONE CALAMAI AND ELENA RUBEI

Abstract. Let X be a finite set. We give a criterion to say if a system of trees P = {T_{i}}_{i} with leaf sets L(T_{i}) ∈ \binom{X}{5} can be amalgamated into a supertree, that is, if there exists a tree T with L(T) = X such that T restricted to L(T_{i}) is equal to T_{i}.

1. Introduction

Phylogenetic trees are used to represent evolutionary relationships among some taxa in many fields, such as biology and philology. Unfortunately, methods to reconstruct phylogenetic trees generally do not work for large numbers of taxa; so it would be useful to have a criterion to say if, given a collection of phylogenetic trees with overlapping sets of taxa, there exists a (super)tree “including” all the trees in the given collection. In this case we say that the collection is “compatible”. The literature on the “supertree problem” is vast. We quote only few of the known results.

One of the first results is due to Colonius and Schultze: in [?] they gave a criterion to say if, given a finite set X, a system of trees P = \{T_{i}\}_{i} with leaf sets L(T_{i}) ∈ \binom{X}{4} can be amalgamated into a supertree, that is, if there exists a tree T with L(T) = X such that T restricted to L(T_{i}) is equal to T_{i}. Obviously, a tree with leaf set {a, b, c, d} is determined by the partition (called “quartet”) of {a, b, c, d} into cherries; Colonius and Schultze defined three properties, thinness, transitivity and saturation, that are necessary and sufficient for a quartet system to be treelike.

In [?] the authors suggest a polynomial time algorithm that, given a collection of trees, produces a supertree, if it exists and under some conditions.

We quote also the papers [?] and [?], where the authors studied closure rules among compatible trees, i.e., rules that, given a compatible collection of trees, determine some other trees not in the original collection.

Finally, in 2012, Grünewald gave a sufficient criterion for a set of binary phylogenetic trees to be compatible; to be precise, he proved that, if P is a finite collection of phylogenetic trees and the cardinality of the union of the leaf sets of the elements of P minus 3 is equal to the sum of the cardinalities of the set of the interior edges of the elements of P, then P is compatible (see [?]).

A possible variant of the supertree problem is to fix the cardinality of the leaf sets of the trees in the given collection. In this paper we consider this problem in the case the cardinality of the leaf set of every tree in the given collection is 5. Obviously a tree with cardinality of the leaf set equal to 5 is given by a partition (called “quintet”) of the leaf set into cherries and the complementary of the union of the cherries. We define three properties, analogous to the ones for quartets, that are necessary and sufficient for a quintet system to be treelike.

2010 Mathematics Subject Classification. 05C05.

Key words and phrases. supertrees, quintets.

Acknowledgments. The authors have been supported by the Project PRIN “Varietà reali e complesse: geometria, topologia e analisi armonica”, and by GNSAGA of INdAM. The first author has also been supported by SIR 2014 AnHyC “Analytic aspects in complex and hypercomplex geometry” (code RBSI14DYEB); he also wants to thank Xiuxiong Chen for constant support.

2. Notation and review

Definition 1. • Let Y be a set. A partition of Y into k subsets of cardinality n_{1}, …, n_{k}, with n_{1} ≥ … ≥ n_{k}, is called a partition of type (n_{1}, …, n_{k}).

• Let X be set.

A partition of a 4-subset Y of X is called a quartet (on Y) in X if its type is (2, 2) or (4).

A partition of a 5-subset Y of X is called a quintet (on Y) in X if its type is (2, 2, 1), (3, 2), or (5).

Any subset of the set of all quartets in X is called a quartet system over X.

Any subset of the set of all quintets in X is called a quintet system over X.

Notation 2. Throughout the paper, X will denote a finite nonempty set.

Definition 3. Let T be a tree.

• We denote by L(T) the leaf set of T.

• For any S ⊂ L(T), we denote by T |_{S} the minimal subtree of T whose vertex set contains S.

• We say that two leaves i and j of T are neighbours if in the path from i to j there is only one vertex of degree greater than 2; furthermore, we say that C ⊂ L(T) is a cherry if any i, j ∈ C are neighbours.

• We say that a cherry is complete if it is not strictly contained in another cherry.

• We say that a tree is a star tree if it has only one vertex of degree greater than or equal to 3.

Definition 4. A phylogenetic X-tree (T, φ) is a finite tree T without vertices of degree 2 and endowed with a bijective function φ : X → L(T).

The quartet system S over X associated with a phylogenetic X-tree is the quartet system defined as follows: for any a, b, c, d ∈ X,

(a, b | c, d) ∈ S if and only if {a, b} and {c, d} are complete cherries of T |_{{a,b,c,d}}, (a, b, c, d) ∈ S if and only if T |_{{a,b,c,d}} is a star tree. The quintet system S over X associated with a phylogenetic X-tree is the

quintet system defined as follows: for any a, b, c, d, e ∈ X, (a, b | c, d | e) ∈ S if and only if {a, b} and {c, d} are complete cherries of T |_{{a,b,c,d,e}}, (a, b | c, d, e) ∈ S if and only if {a, b} and {c, d, e} are complete cherries of T |_{{a,b,c,d,e}}, (a, b, c, d, e) ∈ S if and only if T |_{{a,b,c,d,e}} is a star tree. Given a quartet system (respectively a quintet system) S over X and a quartet (respec-

tively a quintet) in X, we often write either simply “P ” or “P holds” instead of writing “P ∈ S” when it is clear from the context to which system we are referring.

Remark 5. Let X be a set with 4 or 5 elements. Observe that a phylogenetic X-tree is determined by the partition of X into cherries. So we can say that a quartet on a 4-set X represents a tree with 4 leaves (the elements of X), while a quintet on a 5-set X gives a tree with 5 leaves (the elements of X).

In biology, phylogenetic trees represent the evolutionary relationships among some species. In particular, biologists try to reconstruct the trees representing the evolution of species from molecular sequence data from genomes. They often have the evolutionary relationships among small subsets of species and try to reconstruct the more general evolutionary tree by “patching” the trees representing the evolutionary relationships among the small subsets of species. So, in biology, the quartet (or the quintet) systems represent families of 4-taxon trees (respectively 5-taxon trees).

Example. Let X = {1, 2, 3, 4, 5, 6}, and let T be the phylogenetic X-tree in Figure ??, where we have labelled every leaf with the corresponding element of X. In this example, {1, 2, 3} and {4, 5} are the complete cherries of the tree. The quartet system associated with the tree is the following:

{(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2 | 4, 5), (1, 2 | 4, 6), (1, 2 | 5, 6), (1, 3 | 4, 6), (1, 3 | 5, 6),

(1, 3 | 4, 5), (1, 6 | 4, 5), (2, 3 | 4, 5), (2, 3 | 4, 6), (2, 3 | 5, 6), (2, 6 | 4, 5), (3, 6 | 4, 5)}.

Finally, the quintet system associated with the tree is the following:

{(1, 2, 3 | 4, 5), (1, 2, 3 | 4, 6), (1, 2, 3 | 5, 6), (1, 2 | 4, 5 | 6), (1, 3 | 4, 5 | 6), (2, 3 | 4, 5 | 6)}.

6 2 1 3 5 4

Figure 1. A phylogenetic tree

Definition 6. Let S be a quartet system over X.

• We say that S is saturated if the following implication holds for any a_{1}, a_{2}, b_{1}, b_{2}, x ∈ X:

(a_{1}, a_{2} | b_{1}, b_{2}) ⇒ (a_{1}, x | b_{1}, b_{2}) ∨ (a_{1}, a_{2} | b_{1}, x).

• We say that S is transitive if the following implication holds for any a_{1}, a_{2}, b_{1}, b_{2}, x ∈ X:

(a_{1}, x | b_{1}, b_{2}) ∧ (a_{2}, x | b_{1}, b_{2}) ⇒ (a_{1}, a_{2} | b_{1}, b_{2}).

• We say that S is thin if, for any 4-subset Y of X, there exists only one quartet on Y in S.

As we have already said in the introduction, Colonius and Schultze characterized treelike quartet systems. The statement we recall here is the one in [?].

Theorem 7. Let S be a quartet system over X. Then S is the quartet system of a phylogenetic X-tree if and only if S is thin, transitive, and saturated.

Notation 8. Let a_{1}, a_{2}, b_{1}, b_{2}, b_{3} ∈ X, and let Q be a quintet system over X. We write (a_{1}, a_{2} | \overline{b_{1}, b_{2}, b_{3}}) instead of

(a_{1}, a_{2} | b_{1}, b_{2}, b_{3}) ∨ (a_{1}, a_{2} | b_{1}, b_{2} | b_{3}) ∨ (a_{1}, a_{2} | b_{1}, b_{3} | b_{2}) ∨ (a_{1}, a_{2} | b_{2}, b_{3} | b_{1})

Definition 9. Let Q be a quintet system over X.

• We say that Q is saturated if the following implications hold for any a_{i}, b_{j}, c, x ∈ X: (i) (a_{1}, a_{2} | b_{1}, b_{2} | c) ⇒ (a_{1}, a_{2} | b_{1}, b_{2} | x) ∨ (a_{1}, x | b_{1}, b_{2} | c) ∨ (a_{1}, a_{2} | b_{1}, x | c), (ii) (a_{1}, a_{2} | b_{1}, b_{2}, b_{3}) ⇒ (a_{1}, x | b_{1}, b_{2}, b_{3}) ∨ (a_{1}, a_{2} | \overline{b_{1}, b_{2}, x}), (iii) (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) ⇒ (a_{1}, a_{2}, a_{3}, a_{4}, x) ∨ (a_{1}, x | a_{2}, a_{3}, a_{4})

∨(a_{2}, x | a_{1}, a_{3}, a_{4}) ∨ (a_{3}, x | a_{1}, a_{2}, a_{4}) ∨ (a_{4}, x | a_{1}, a_{2}, a_{3}).

• We say that Q is transitive if the following implications hold for any a_{i}, b_{j}, c_{k}, x ∈ X:

(i) (a_{1}, a_{2} | b_{1}, x | c_{1}) ∧ (a_{1}, a_{2} | b_{1}, x | c_{2}) ⇒ (a_{1}, a_{2} | \overline{c_{1}, c_{2}, b_{1}}),

(ii) (a_{1}, a_{2} | b_{1}, x | c_{1}) ∧ (a_{1}, a_{2} | b_{2}, x | c_{1}) ⇒ (a_{1}, a_{2} | b_{1}, b_{2} | c_{1}), (iii) (a_{1}, x | b_{1}, b_{2}, b_{3}) ∧ (a_{2}, x | b_{1}, b_{2}, b_{3}) ⇒ (a_{1}, a_{2} | b_{1}, b_{2}, b_{3}), (iv) (a_{1}, a_{2} | b_{1}, b_{3}, x) ∧ (a_{1}, a_{2} | b_{2}, b_{3}, x) ⇒ (a_{1}, a_{2} | b_{1}, b_{2}, b_{3}) ∨ (a_{1}, a_{2} | b_{1}, b_{2} | b_{3}),

(v) (a_{1}, a_{2} | b_{1}, x, b_{2}) ∧ (a_{1}, a_{2} | b_{1}, x | b_{3}) ⇒ (a_{1}, a_{2} | b_{1}, b_{2} | b_{3}), (vi) (a_{1}, a_{2} | b_{1}, b_{2} | x) ∧ (a_{1}, a_{2} | b_{1}, b_{3}, x) ⇒ (a_{1}, a_{2} | b_{1}, b_{2} | b_{3}).

• We say that Q is thin if, for any 5-subset Y of X, there exists only one quintet on Y in Q and, for any a, b, c, d, x, y ∈ X,

(i) (a, b | c, x | d) ∧ (a, c | b, y | d) is impossible,

(ii) (a, b | c, d, x) ∧ (a, y | b, c, d) is impossible,

(iii) (a, b | c, x | d) ∧ (a, c, d | b, y) is impossible,

(iv) (a, x | b, c, d) ∧ (a, d | b, c | y) is impossible.

Both for quartet systems and quintet systems, we will write TTS instead of thin, transitive and saturated.

3. Characterization of treelike quintet systems

Our aim is the proof that a quintet system is treelike if and only if it is TTS.

First of all, we need to define the quartet system associated with a quintet system and the quintet system associated with a quartet system.

Definition 10. Given a TTS quintet system Q over X, let S be the quartet system defined as follows: for any a, b, c, d ∈ X, we have (a, b | c, d) ∈ S if and only if there exists y ∈ X for which at least one of the following instances occurs:

(i) (a, b | c, d | y) ∈ Q,

(ii) (a, b | c, d, y) ∈ Q,

(iii) (a, b | c, y | d) ∈ Q,

(iv) (a, b | d, y | c) ∈ Q,

(v) (c, d | b, y | a) ∈ Q,

(vi) (c, d | a, y | b) ∈ Q,

(vii) (a, b, y | c, d) ∈ Q. We say that S is the quartet system associated with the quintet system Q.

Definition 11. Let S be a TTS quartet system over X. Let Q′ be the quintet system over X defined by:

(a, b | c, d | e) ∈ Q′ if and only if (a, b | c, d), (a, b | c, e), (a, e | c, d) ∈ S,

(a, b | c, d, e) ∈ Q′ if and only if (a, b | c, d), (a, b | c, e), (a, e, c, d), (b, c, d, e) ∈ S, (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) ∈ Q′ if and only if (a_{1}, …., â_{i}, …., a_{5}) ∈ S for any i ∈ {1, …., 5}.

We say that Q′ is the quintet system associated with the quartet system S.

The sketch of the proof of our result (given in Theorem ??) is the following: given a TTS quintet system Q, we will show that the associated quartet system S is TTS; so there exists a phylogenetic X-tree (T, φ) inducing S. We will show that the quintet system associated with (T, φ) is exactly Q, and this will end the proof.

First, we have to state two lemmas which will be useful in the remainder of the paper.

Lemma 12. Let Q be a TTS quintet system over X. For any a, b, c, d, x, y ∈ X, it is not possible to have the simultaneous occurrence of

(A) (a, b | c, x | d) and any of the following:

(B) (a, c | b, d | y), (C) (a, c | d, y | b), (D) (b, d | c, y | a), (E) (y, c | a, b, d), (F) (a, c | b, d, y), (G) (a, d | b, c, y), (H) (d, y | a, b, c).

Proof. As Q is saturated, (A) implies at least one of the following cases: (A.1) (a, y | c, x | d) ∧ (y, b | c, x | d), (A.2) (a, b | c, y | d) ∧ (a, b | x, y | d), (A.3) (a, b | c, x | y).

We claim that (A) ∧ (B) cannot hold. As Q is saturated, (B) implies at least one of the following: (B.1) (a, x | b, d | y) ∧ (x, c | b, d | y), (B.2) (a, c | x, d | y) ∧ (a, c | b, x | y), (B.3) (a, c | b, d | x). Since Q is thin, each of (A)∧(B.3), (A.1)∧(B.1), (A.1)∧(B.2), (A.2)∧(B), (A.3)∧(B.2) is impossible. As Q is transitive, (A) ∧ (A.3) implies (a, b | \overline{d, x, y}), which contradicts (B.1); thus the claim is proved.

We now show that (A) ∧ (C) cannot hold. As Q is saturated, (C) implies at least one of the following: (C.1) (a, x | d, y | b) ∧ (x, c | d, y | b), (C.2) (a, c | d, x | b), (C.3) (a, c | d, y | x). Since Q is thin, each of (A) ∧ (C.2), (A.1) ∧ (C.1), (A.1) ∧ (C.3), (A.2) ∧ (C) is impossible. As Q is transitive, (A) ∧ (A.3) implies (a, b | \overline{c, d, y}), which contradicts (C), yielding the claim.

6 SIMONE CALAMAI AND ELENA RUBEI

We prove that (A) ∧ (D) cannot hold. As Q is saturated, (D) implies at least one of the following: (D.1) (x, d | c, y | a) ∧ (b, x | c, y | a), (D.2) (b, d | c, x | a), (D.3) (b, d | c, y | x). Since Q is thin, it is impossible to have each of (A) ∧ (D.2), (A.1) ∧ (D.1), (A.1) ∧ (D.3), (A.2) ∧ (D). As Q is transitive, (A) ∧ (A.3) implies (a, b | \overline{c, d, y}), which contradicts (D), yielding the claim.

We claim that (A) ∧ (E) is impossible. As Q is saturated, (E) implies

(x, c | a, b, d) (E.1) ∨ [(y, c | \overline{a, b, x}) (E.2) ∧ (y, c | \overline{a, d, x}) (E’.2)].

The thinness of Q excludes each of (A) ∧ (E.1), (A.1) ∧ (E’.2), (A.2) ∧ (E), (A.3) ∧ (E.2), yielding the claim.

We claim that (A) ∧ (F) cannot hold. As Q is saturated, (F) implies at least one of the following: (F.1) (a, x | b, d, y) ∧ (c, x | b, d, y), (F.2) (a, c | \overline{b, d, x}). As Q is thin, each of (A)∧(F.2), (A.1)∧(F.1), (A.2)∧(F.1) is impossible. Moreover, since Q is transitive, (A.3) ∧ (A) implies (a, b | \overline{d, x, y}), which contradicts (F.1) by the thinness of Q, so the claim follows.

We claim that (A) ∧ (G) cannot hold. As Q is saturated, (G) implies at least one of the following: (G.1) (a, x | b, c, y) ∧ (d, x | b, c, y), (G.2) (a, d | \overline{b, c, x}). By the thinness of Q, each of (A) ∧ (G.2), (A.1) ∧ (G.1), (A.2) ∧ (G), (A.3) ∧ (G.1) is impossible, so we get the claim.

We claim that (A) ∧ (H) cannot hold. As Q is saturated, (H) implies at least one of the following: (H.1) (d, x | a, b, c), (H.2) (d, y | \overline{a, c, x}). By the thinness of Q, each of (A) ∧ (H.1), (A.1) ∧ (H.2), (A.2) ∧ (H) is impossible. Moreover, since Q is transitive, (A.3) ∧ (A) implies (a, b | \overline{d, c, y}), which contradicts (H) by the thinness of Q, so the claim follows. □ Lemma 13. Let Q be a TTS quintet system over X. For any a, b, c, d, x, y ∈ X, it is not possible to have the simultaneous occurrence of

(A) (a, c | b, d, y) and any of the following:

(B) (b, x | a, c, d), (C) (a, b | c, d | x).

Proof. As Q is saturated, (A) implies at least one of (A.1) (a, x | b, d, y) ∧ (c, x | b, d, y), (A.2) (a, c | \overline{b, d, x}), and (B) implies at least one of (B.1) (b, y | a, c, d), (B.2) (b, x | \overline{a, d, y}). As Q is thin, each of (B) ∧ (A.2), (B.1) ∧ (A), (B.2) ∧ (A.1) is impossible, which concludes the proof that (A) ∧ (B) cannot hold.

Since Q is saturated, from (C) we get at least one of the following: (C.1) (a, y | c, d | x) ∧ (b, y | c, d | x), (C.2) (a, b | c, y | x) ∧ (a, b | d, y | x), (C.3) (a, b | c, d | y). By the thinness of Q, each of (C) ∧ (A.2), (C.1) ∧ (A.1), (C.2) ∧ (A.1) cannot hold. Moreover, (C.3) ∧ (C) implies (a, b | \overline{d, x, y}), which contradicts (A.1), and this concludes the proof that (A) ∧ (C) cannot hold. □

Proposition 14. Let Q be a TTS quintet system over X. Let a_{1}, a_{2}, b_{1}, b_{2} ∈ X. There exists x ∈ X such that at least one of

(1) (a_{1}, a_{2} | b_{1}, b_{2} | x),

(2) (a_{1}, a_{2} | b_{1}, b_{2}, x),

(3) (a_{1}, a_{2}, x | b_{1}, b_{2}),

(4) (a_{1}, a_{2} | b_{1}, x | b_{2}),

(5) (a_{1}, a_{2} | b_{2}, x | b_{1}),

(6) (a_{1}, x | b_{1}, b_{2} | a_{2}),

(7) (a_{2}, x | b_{1}, b_{2} | a_{1}) holds, if and only if for any x ∈ X at least one of (1)–(7) holds.

Proof. ⇐ Obvious.

⇒ Suppose, contrary to our claim, that there exists y ∈ X such that none of (1)–(7) holds (with y instead of x). So we must have at least one of the following:

(8) (a_{1}, a_{2}, b_{1}, b_{2}, y)

(9) (a_{i}, b_{j} | a_{l}, b_{r}, y) for some i, l, j, r with {i, l} = {1, 2} = {j, r},

(10) (a_{i}, y | a_{l}, b_{1}, b_{2}) for some i, l with {i, l} = {1, 2},

(11) (b_{i}, y | b_{l}, a_{1}, a_{2}) for some i, l with {i, l} = {1, 2},

(12) (a_{i}, b_{j} | a_{l}, b_{r} | y) for some i, l, j, r with {i, l} = {1, 2} = {j, r},

(13) (a_{i}, y | a_{l}, b_{j} | b_{r}) for some i, l, j, r with{i, l} = {1, 2} = {j, r},

(14) (b_{j}, y | b_{r}, a_{i} | a_{l}) for some i, l, j, r with{i, l} = {1, 2} = {j, r}.

Case 1: condition (1) holds. By the saturation of Q, this implies at least one of the following: (1.1) (a_{1}, y | b_{1}, b_{2} | x) ∧ (a_{2}, y | b_{1}, b_{2} | x), (1.2) (a_{1}, a_{2} | b_{1}, y | x) ∧ (a_{1}, a_{2} | b_{2}, y | x), (1.3) (a_{1}, a_{2} | b_{1}, b_{2} | y).

• Suppose (8) holds. Since Q is saturated, (8) implies (a_{1}, a_{2}, b_{1}, b_{2}, x)∨(a_{i}, x | a_{j}, b_{1}, b_{2})∨ (b_{i}, x | b_{j}, a_{1}, a_{2}) for some i, j with {i, j} = {1, 2}, which contradicts (1).

• Suppose (9) holds. We may suppose that i = j = 1 and l = r = 2 in (9), so (a_{1}, b_{1} | a_{2}, b_{2}, y) holds. We get a contradiction by Lemma ??, Case (C).

• Suppose (10) holds. We may suppose that i = 1 in (10), so (a_{1}, y | a_{2}, b_{1}, b_{2}) holds. However, by the thinness of Q, this is impossible.

• Suppose (11) holds. This case is analogous to the previous case (by swapping (a_{1}, a_{2}) with (b_{1}, b_{2})).

• Suppose (12) holds. We may suppose that i = j = 1 in (12), so (a_{1}, b_{1} | a_{2}, b_{2} | y) holds. By the saturation of Q, this implies at least one of the following: (12.1) (a_{1}, x | a_{2}, b_{2} | y) ∧ (b_{1}, x | a_{2}, b_{2} | y), (12.2) (a_{1}, b_{1} | a_{2}, x | y) ∧ (a_{1}, b_{1} | b_{2}, x | y), (12.3) (a_{1}, b_{1} | a_{2}, b_{2} | x). Observe that (1.1) contradicts both (12.1) and (12.2), (1.2) contradicts both (12.1) and (12.2), (1.3) contradicts (12), and, finally, (12.3) contradicts (1).

• Suppose (13) holds. We may suppose i = r = 1, so (y, a_{1} | a_{2}, b_{2} | b_{1}) holds. We get a contradiction by Lemma ??, Case (B).

• Suppose (14) holds. This case is analogous to the previous case (by swapping (a_{1}, a_{2}) with (b_{1}, b_{2})).

Case 2: condition (2) holds. By the saturation of Q, this implies at least one of (2.1) (a_{1}, y | b_{1}, b_{2}, x) ∧ (a_{2}, y | b_{1}, b_{2}, x), (2.2) (a_{1}, a_{2} | \overline{b_{1}, b_{2}, y}).

• Suppose (8) holds. By the saturation of Q, we have

(a_{i}, x | b_{1}, b_{2}, a_{j}) ∨ (b_{r}, x | a_{1}, a_{2}, b_{l}) ∨ (a_{1}, a_{2}, b_{1}, b_{2}, x)

for some i, j with {i, j} = {1, 2} and some r, l with {r, l} = {1, 2}. All the possibilities contradict (2).

• Suppose (9) holds. We may suppose i = j = 1. So (a_{1}, b_{1} | a_{2}, b_{2}, y) holds. By the saturation of Q, this implies at least one of the following: (9.1) (a_{1}, x | a_{2}, b_{2}, y) ∧ (b_{1}, x | a_{2}, b_{2}, y), (9.2) (a_{1}, b_{1} | \overline{a_{2}, b_{2}, x}). Observe that (2.2) contradicts (9) and (9.2) contradicts (2). Moreover, (2.1) contradicts (9.1).

• Suppose (10) holds. Since Q is thin, we get a contradiction.

• Suppose (11) holds. We may suppose i = 1, and we get a contradiction by Lemma ??, Case (B).

• Suppose (12) holds. We get a contradiction by Lemma ??, Case (C).

• Suppose (13) holds. We may suppose i = r = 1, so (y, a_{1} | a_{2}, b_{2} | b_{1}) holds. We get a contradiction by Lemma ??, Case (F).

• Suppose (14) holds. We may suppose j = l = 1, so (y, b_{1} | a_{2}, b_{2} | a_{1}) holds. We get a contradiction by Lemma ??, Case (G).

Case 3: condition (3) holds. This case is analogous to Case 2 (swap (a_{1}, a_{2}) with (b_{1}, b_{2})).

Case 4: condition (4) holds. By the saturation of Q, this implies at least one of the following: (4.1) (a_{1}, y | b_{1}, x | b_{2}) ∧ (a_{2}, y | b_{1}, x | b_{2}), (4.2) (a_{1}, a_{2} | b_{1}, y | b_{2}), (4.3) (a_{1}, a_{2} | b_{1}, x | y).

• Suppose (8) holds. By the saturation of Q, Condition (8) implies

(a_{1}, a_{2}, b_{1}, b_{2}, x) ∨ (a_{1}, x | a_{2}, b_{1}, b_{2}) ∨ (a_{2}, x | a_{1}, b_{1}, b_{2}) ∨ (b_{1}, x | a_{1}, a_{2}, b_{2}) ∨ (b_{2}, x | a_{1}, a_{2}, b_{1}),

which contradicts (4).

• Suppose (9) holds.

First case: i = j = 1 in (9). So we have (a_{1}, b_{1} | a_{2}, b_{2}, y). By Lemma ??, Case (F), we get a contradiction.

Second case: i = r = 1 in (9). So we have (a_{1}, b_{2} | a_{2}, b_{1}, y). We get a contradiction by Lemma ??, Case (G).

• Suppose (10) holds. We may suppose i = 1 in (10). Since Q is thin, (4) contradicts (10).

• Suppose (11) holds.

First suppose that i = 1 in (11). This is impossible by Lemma ??, Case (E).

Now suppose that i = 2 in (11). This is impossible by Lemma ??, Case (H).

• Suppose (12) holds. We may suppose i = j = 1. By Lemma ??, Case (B), we get a contradiction.

• Suppose (13) holds. We may suppose i = 1. If r = 1, we get a contradiction by Lemma ??, Case (C). If r = 2, we get a contradiction by the thinness of Q.

• Suppose (14) holds. We may suppose l = 1. If j = 1, we get a contradiction by Lemma ??, Case (D). If j = 2, we get a contradiction by Lemma ??, Case (C).

Case 5: condition (5) holds. This case is analogous to Case 4 (swap b_{1} with b_{2}).

Case 6: condition (6) holds. This case is analogous to Case 4 (swap a_{1} with b_{1} and a_{2} with b_{2}).

Case 7: condition (7) holds. This case is analogous to Case 6 (swap a_{1} with a_{2}). □

The next goal is to prove that a quartet system S as in Definition ?? is in fact TTS.

Proposition 15. A quartet system S associated with a TTS quintet system Q as in Definition ?? is thin.

Proof. Assume, by contradiction, that (a, b | c, d) ∧ (a, c | b, d) holds. By Proposition ??, the hypothesis that (a, b | c, d) holds is equivalent to saying that, for any y ∈ X, we have

(a, b | \overline{c, d, y}) ∨ (c, d | \overline{a, b, y}). (1)

Moreover, by Definition ??, the fact that (a, c | b, d) holds means that there exists x ∈ X such that

(a, c | \overline{b, d, x}) ∨ (b, d | \overline{a, c, x}). (2)

If we choose y = x in (??), we get a contradiction with (??) by the thinness of Q. □

Proposition 16. A quartet system S associated with a TTS quintet system Q as in Definition ?? is transitive.

Proof. The goal is to prove

(a_{1}, a_{2} | b_{1}, b_{2}) ∧ (a_{2}, a_{3} | b_{1}, b_{2}) ⇒ (a_{1}, a_{3} | b_{1}, b_{2}).

Recall that, by Proposition ??, (a_{1}, a_{2} | b_{1}, b_{2}) means that, for every x ∈ X, at least one of the following conditions must hold:

(1.1) (a_{1}, a_{2} | b_{1}, b_{2} | x), (1.2) (a_{1}, a_{2} | b_{1}, b_{2}, x), (1.3) (a_{1}, a_{2}, x | b_{1}, b_{2}), (1.4) (a_{1}, a_{2} | b_{1}, x | b_{2}), (1.5) (a_{1}, a_{2} | b_{2}, x | b_{1}), (1.6) (a_{1}, x | b_{1}, b_{2} | a_{2}), (1.7) (a_{2}, x | b_{1}, b_{2} | a_{1}). Similarly, by Proposition ??, (a_{2}, a_{3} | b_{1}, b_{2}) means that, for every x ∈ X, at least one

of the following conditions holds: (2.1) (a_{2}, a_{3} | b_{1}, b_{2} | x), (2.2) (a_{2}, a_{3} | b_{1}, b_{2}, x), (2.3) (a_{2}, a_{3}, x | b_{1}, b_{2}), (2.4) (a_{2}, a_{3} | b_{1}, x | b_{2}), (2.5) (a_{2}, a_{3} | b_{2}, x | b_{1}), (2.6) (a_{2}, x | b_{1}, b_{2} | a_{3}), (2.7) (a_{3}, x | b_{1}, b_{2} | a_{2}). First we are going to show that, for any k ∈ {1, …, 7}, if there exists x such that

(1.k)∧(2.k) holds, then (a_{1}, a_{3} | b_{1}, b_{2}) holds; then we prove that, if there exists x such that one of the remaining pairings holds, then we get either (a_{1}, a_{3} | b_{1}, b_{2}) or a contradiction. Observe that, by symmetry, it is sufficient to consider the cases (1.k) ∧ (2.j) with j > k.

Suppose (1.h) ∧ (2.h) for some x ∈ X and h ∈ {1, …, 5}. Then (a_{1}, a_{3} | b_{1}, b_{2}) follows from the transitivity of Q and Definition ??.

Assume (1.6) ∧ (2.6). Since Q is saturated, (1.6) implies that

(x, a_{3} | b_{1}, b_{2} | a_{2}) (1.6.1) ∨ (a_{1}, x | b_{1}, a_{3} | a_{2}) (1.6.2) ∨ (a_{1}, x | b_{1}, b_{2} | a_{3}) (1.6.3),

and (2.6) implies that

(a_{1}, x | b_{1}, b_{2} | a_{3}) (2.6.1) ∨ (a_{2}, x | b_{1}, a_{1} | a_{3}) (2.6.2) ∨ (a_{2}, x | b_{1}, b_{2} | a_{1}) (2.6.3).

Each of (1.6.1) ∧ (2.6), (2.6.3) ∧ (1.6), (1.6.2) ∧ (2.6.2) contradicts the thinness of Q; moreover, by Definition ??, each of (1.6.3) and (2.6.1) implies (a_{1}, a_{3} | b_{1}, b_{2}) and this allows us to conclude.

The case (1.7) ∧ (2.7) can be recovered from the previous one by swapping a_{1} with a_{3}.

The case (1.1) ∧ (2.2) is impossible by Lemma ??, Case (E).

Assume (1.1)∧(2.3). Since Q is saturated, from (2.3) we get at least one of the following: (2.3.1) (b_{1}, a_{1} | a_{2}, a_{3}, x), (2.3.2) (b_{1}, b_{2} | x, a_{3}, a_{1}), (2.3.3) (b_{1}, b_{2} | x, a_{3} | a_{1}), (2.3.4) (b_{1}, b_{2} | x, a_{1} | a_{3}), (2.3.5) (b_{1}, b_{2} | a_{1}, a_{3} | x). The occurrence of (1.1) ∧ (2.3.1) is impossible by Lemma ??, Case (F).

Each of (2.3.2), (2.3.3), (2.3.4), (2.3.5) allows us to conclude, by Definition ??, that (a_{1}, a_{3} | b_{1}, b_{2}) holds.

The case (1.1) ∧ (2.4) is impossible by Lemma ??, Case (D). Swapping b_{1} with b_{2}, we also get that the case (1.1) ∧ (2.5) is impossible.

TREELIKE QUINTET SYSTEMS 11

Suppose (1.1) ∧ (2.6). Since Q is saturated, (1.1) implies (a_{1}, a_{3} | b_{1}, b_{2} | x) (1.1.1) ∨ (a_{1}, a_{2} | b_{1}, a_{3} | x) (1.1.2) ∨ (a_{1}, a_{2} | b_{1}, b_{2} | a_{3}) (1.1.3), and (2.6) implies one of (2.6.1), (2.6.2), (2.6.3) above. From (1.1.1) as well as from (1.1.3) and from (2.6.1) one can deduce, by means of Definition ??, that (a_{1}, a_{3} | b_{1}, b_{2}) holds; each of (2.6.3) ∧ (1.1) and (1.1.2) ∧ (2.6.2) contradicts the thinness of Q and this allows us to conclude.

Suppose (1.1) ∧ (2.7). Since Q is saturated, (1.1) implies one of (1.1.1), (1.1.2), (1.1.3), and (2.7) implies (a_{1}, a_{3} | b_{1}, b_{2} | a_{2}) (2.7.1) ∨ (a_{3}, x | b_{1}, a_{1} | a_{2}) (2.7.2) ∨ (a_{3}, x | b_{1}, b_{2} | a_{1}) (2.7.3). From (1.1.1) as well as from (1.1.3) and from (2.7.3), one can deduce that (a_{1}, a_{3} | b_{1}, b_{2}) holds. Finally, the case (2.7.1) ∧ (1.1), as well as the case (1.1.2) ∧ (2.7.2), contradicts the thinness of Q, and so we can conclude.

The case (1.2) ∧ (2.3) is impossible by the thinness of Q.

The case (1.2) ∧ (2.4) is impossible by Lemma ??, Case (E). Swapping b_{1} with b_{2}, we also see that the case (1.2) ∧ (2.5) cannot hold.

The case (1.2) ∧ (2.6) is impossible by the thinness of Q.

The case (1.2) ∧ (2.7) cannot hold by Lemma ??, Case (H).

The case (1.3) ∧ (2.4) cannot hold by Lemma ??, Case (G).

The case (1.3) ∧ (2.5) is analogous to the previous one swapping b_{1} with b_{2}.

Assume (1.3) ∧ (2.6). Since Q is saturated, (1.3) implies

(b_{1}, a_{3} | a_{1}, a_{2}, x) (1.3.1) ∨ (b_{1}, b_{2} | \overline{a_{1}, a_{2}, a_{3}}) (1.3.2),

and, similarly, (2.6) implies one of (2.6.k), k = 1, 2, 3. From (2.6.1), as well as from (1.3.2), one can deduce that (a_{1}, a_{3} | b_{1}, b_{2}) holds. Moreover, (2.6.3) ∧ (1.3), as well as (2.6.2) ∧ (1.3.1), contradicts the thinness of Q, and so we conclude.

Assume (1.3) ∧ (2.7). Since Q is saturated, (1.3) implies one of (1.3.1), (1.3.2), and (2.7) implies one of (2.7.1), (2.7.2), (2.7.3). Observe that each of (1.3.2), (2.7.1), (2.7.3) implies (a_{1}, a_{3} | b_{1}, b_{2}). Moreover, (1.3.1) ∧ (2.7.2) contradicts the thinness of Q.

Cases (1.4) ∧ (2.5), (1.4) ∧ (2.6), (1.4) ∧ (2.7) are impossible by Lemma ??, Cases (D), (B), (C), respectively.

Assume (1.5)∧(2.6). Then, by swapping b_{1} with b_{2}, one gets back to the case (1.4)∧(2.6). Suppose (1.5) ∧ (2.7). Then, by swapping b_{1} with b_{2}, one gets back to the case (1.4) ∧

(2.7).

Assume (1.6) ∧ (2.7). Then, by transitivity of Q, one gets (a_{1}, a_{3} | b_{1}, b_{2} | a_{2}), and by Definition ?? one can deduce (a_{1}, a_{3} | b_{1}, b_{2}). □ Proposition 17. A quartet system S associated with a TTS quintet system Q as in Definition ?? is saturated. Proof. Suppose that (a_{1}, a_{2} | b_{1}, b_{2}) and fix x ∈ X. By Definition ??, there exists z ∈ X such that at least one of the following holds:

(1) (z | a_{1}, a_{2} | b_{1}, b_{2}), (2) (a_{1}, a_{2} | b_{1}, b_{2}, z),

(3) (a_{1}, a_{2} | b_{1}, z | b_{2}),

(4) (a_{1}, a_{2} | b_{2}, z | b_{1}),

(5) (b_{1}, b_{2} | a_{1}, z | a_{2}),

(6) (b_{1}, b_{2} | a_{2}, z | a_{1}),

(7) (b_{1}, b_{2} | a_{1}, a_{2}, z).

The argument consists in showing that any of the items above implies either (a_{1}, a_{2} | b_{1}, x) or (a_{1}, x | b_{1}, b_{2}). Since it is repetitive, and uses essentially only Definition ??, we only give a sample of the whole argument.

Suppose that (4) holds. Then, as Q is saturated, we have

(a_{1}, a_{2} | b_{2}, z | x) (4.1) ∨ (a_{1}, x | b_{2}, z | b_{1}) (4.2) ∨ (a_{1}, a_{2} | b_{2}, x | b_{1}) (4.3).

By Item (iv) of Definition ?? with a = a_{1}, b = a_{2}, c = x, d = b_{2}, y = z, Condition (4.1) entails (a_{1}, a_{2} | x, b_{2}). Since also (a_{1}, a_{2} | b_{1}, b_{2}) ∈ S, the hypothesis that S is transitive allows us to obtain (a_{1}, a_{2} | b_{1}, x).

By (iv) of Definition ?? with a = a_{1}, b = x, c = b_{1}, d = b_{2}, y = z, Case (4.2) entails (a_{1}, x | b_{1}, b_{2}).

By (iv) of Definition ?? with a = a_{1}, b = a_{2}, c = b_{1}, d = x, y = b_{2}, Case (4.3) entails (a_{1}, a_{2} | b_{1}, x), as desired. □

Remark 18. Let S be the quartet system of a phylogenetic X-tree (T, φ), and let Q′ be the quintet system over X associated with S. Then Q′ is the quintet system of (T, φ).

Remark 19. Let Q be a TTS quintet system over X; call S the quartet system associated with Q. We have that (a, b, c, d) ∈ S if and only if

(3) (a, b, c, d, x) ∈ Q ∨ (a, x | b, c, d) ∈ Q ∨ (b, x | a, c, d) ∈ Q ∨ (c, x | a, b, d) ∈ Q ∨ (d, x | a, b, c) ∈ Q

for any x ∈ X. By Proposition ??, this holds if and only if there exists x ∈ X such that (??) holds.

Proposition 20. Let Q be a TTS quintet system over X; call S the quartet system associated with Q and Q′ the quintet system associated with S. Then Q = Q′.

Proof. First we prove that every partition of Q′ of type (2, 2, 1) or of type (2, 3) is also an element of Q.

Let (a, b | c, d | e) ∈ Q′. Suppose that (a, b | c, d | e) ∉ Q. Thus one of the following conditions holds:

(1) (a, b, c, d, e) ∈ Q; by the definition of S, this would imply (a, b, c, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S (and S is thin).

(2) (x, y | z, w, u) ∈ Q for {x, y, z, w, u} = {a, b, c, d, e}; by the definition of S, this would imply (x, z, w, u) ∈ S, which is absurd since, by the definition of Q′, a partition of type (2, 2) of {x, z, w, u} is in S (and S is thin).

(3) A partition of type (2, 2, 1) of {a, b, c, d, e}, different from (a, b | c, d | e), is in Q; up to swapping a with b or c with d or {a, b} with {c, d}, we can suppose (a, c | b, d | e) ∈ Q or (a, e | c, d | b) ∈ Q or (a, e | b, d | c) ∈ Q.

By the definition of S, (a, c | b, d | e) ∈ Q would imply (a, c | b, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S (and S is thin).

By the definition of S, (a, e | c, d | b) ∈ Q would imply (a, e | b, c) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, e) ∈ S (and S is thin).

By the definition of S, (a, e | b, d | c) ∈ Q would imply (a, c | b, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S (and S is thin).

Let (a, b | c, d, e) ∈ Q′. Suppose that (a, b | c, d, e) ∉ Q. Thus one of the following conditions holds:

(1) (a, b, c, d, e) ∈ Q; by Remark ??, this would imply (a, b, c, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S (and S is thin).

(2) A partition of type (2, 3) of {a, b, c, d, e}, different from (a, b | c, d, e), is in Q; up to making a permutation of {a, b} or of {c, d, e}, we may suppose (a, c | b, d, e) ∈ Q or (c, d | a, b, e) ∈ Q.

The condition (a, c | b, d, e) ∈ Q would imply (a, c | b, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S.

The condition (c, d | a, b, e) ∈ Q would imply (c, d | b, e) ∈ S, which is absurd since, by the definition of Q′, we have (b, c, d, e) ∈ S.

(3) A partition of type (2, 2, 1) of {a, b, c, d, e} is in Q; up to making a permutation of {a, b} or of {c, d, e}, we may suppose (a, b | c, d | e) ∈ Q or (a, c | d, e | b) ∈ Q or (a, c | b, d | e) ∈ Q or (c, d | b, e | a) ∈ Q.

The condition (a, b | c, d | e) ∈ Q would imply (b, e | c, d) ∈ S, which is absurd since, by the definition of Q′, we have (b, c, d, e) ∈ S.

The condition (a, c | d, e | b) ∈ Q would imply (a, c | b, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S.

The condition (a, c | b, d | e) ∈ Q would imply (a, c | b, d) ∈ S, which is absurd since, by the definition of Q′, we have (a, b | c, d) ∈ S.

The condition (c, d | b, e | a) ∈ Q would imply (c, d | b, e) ∈ S, which is absurd since, by the definition of Q′, we have (c, d, b, e) ∈ S.

Now we prove that every partition of Q of type (2, 2, 1) or of type (2, 3) is also an element of Q′.

Let (a, b | c, d | e) ∈ Q. By the definition of Q′, we have that (a, b | c, d | e) ∈ Q′ if and only if (a, b | c, d) ∈ S ∧ (a, b | c, e) ∈ S ∧ (a, e | c, d) ∈ S, and this follows from the fact that (a, b | c, d | e) ∈ Q and the definition of S.

Let (a, b | c, d, e) ∈ Q. By the definition of Q′, we have that (a, b | c, d, e) ∈ Q′ if and only if (a, b | c, d) ∈ S ∧ (a, b | c, e) ∈ S ∧ (a, e, c, d) ∈ S ∧ (b, c, d, e) ∈ S, and this follows from the fact that (a, b | c, d, e) ∈ Q and the definition of S. □

Theorem 21. Let Q be a quintet system over X. The system Q is the quintet system of a phylogenetic X-tree if and only if Q is TTS.

Proof. ⇒ This direction is very easy to prove.

⇐ By Propositions ??, ?? and ??, the quartet system S associated with Q is TTS. So, by Theorem ??, there exists an X-tree (T, φ) whose quartet system is S. Let Q′ be the quintet system associated with S. By Remark ??, the system Q′ is the quintet system associated with (T, φ). By Proposition ??, we have Q = Q′, hence Q is the quintet associated with (T, φ). □

References

[1] S. Böcker, D. Bryant, A. Dress, M. Steel, Algorithmic aspects of tree amalgamation, J. Algorithms 37 (2000), 522–537.

[2] D. Bryant, M. Steel, Extension operations on sets of leaf-labelled trees, Adv. Appl. Math. 16 (1995), 425–453.

[3] H. Colonius, H. H. Schultze, Tree structure from proximity data, British J. Math. Statist. Psychology 34 (1981), 167–180.

[4] A. Dress, K. T. Huber, J. Koolen, V. Moulton, A. Spillner, Basic phylogenetic combinatorics, Cambridge University Press, Cambridge, 2012.

[5] S. Grünewald, M. Steel, M. Shel Swenson, Closure operations in phylogenetics, Math. Biosci. 208 (2007), 521–537.

[6] S. Grünewald, Slim sets of binary trees, J. Combin. Theory Ser. A 119 (2012), 323–330.

Dipartimento di Matematica e Informatica “U. Dini”, viale Morgagni 67/A, 50134 Firenze, Italia

  E-mail address: scalamai@math.unifi.it, rubei@math.unifi.it