Wiki source code of Split

Last modified by 14zunde on 2024/02/13 07:41
Show last authors
1 A split can be thought of a division of a [[set>>doc:stemmatology.Set.WebHome]] into two disjoint subsets. More precisely, a split of a set //X// is a partition of //X// into two, non-empty, disjoint sets //A// and //B//, so that the union of //A// and //B// is equal to //X//. For example, { {French, English} , {Chinese, Russian, Italian} } is a split of the set {French, English, Chinese, Russian, Italian}. To ease notation, a split {//A,B//} of a set //X// is sometimes denoted by //A|B// (or //B|A// as the order in which //A// and //B// are listed does not matter). Using this notation, the split above becomes {French, English} | {Chinese, Russian, Italian}.
2
3 ==== Trivial split ====
4
5 A //trivial split// of a set //X// is any split of //X// of the form {//x//}| //X//-{//x//}, where //x// is some element of //X//. For example, {French} | {Chinese, Russian, Italian} is a trivial split of the set {French, Chinese, Russian, Italian}.
6
7 ==== Split system ====
8
9 A //split system// ∑ on a set //X// is a set of splits of //X//. For example, { {French, English} | {German, Italian}, {French, German} | {English, Italian} }, is a split system on the set {French, English, German, Italian}, that contains two splits.
10
11 ==== Compatible splits (incompatible splits) ====
12
13 Two distinct splits //A//|//B// and //C//|//D// of a set are called //compatible// if one of the intersections //A// ∩ //C//, //A// ∩ //D//, //B// ∩ //C//, and //B// ∩ //D// is empty. Two splits are called //incompatible// if they are not compatible. Note that in a [[phylogenetic tree>>doc:stemmatology.Phylogenetic tree.WebHome]] with [[leaf>>doc:stemmatology.Leaf.WebHome]] set //X//, each of the [[edges>>doc:stemmatology.Edge.WebHome]] induces a split of //X//, and that the two splits induced by any pair of distinct edges in the [[tree>>doc:stemmatology.Tree.WebHome]] are compatible.
14
15 ==== Compatible split system ====
16
17 A //compatible// split system on a set //X// is a split system on //X// in which any pair of splits is compatible. Note that it was proved by Peter Buneman (1971) that a compatible split system which contains all possible trivial splits can always be represented by a (unique) phylogenetic tree with leaf set //X// (see e.g. Theorem 3.1.4 [2]). In particular, each of the edges in the tree represents a split since its removal from the tree cuts the tree into two pieces which gives a split of the leaf set //X//. This implies that a split system ∑ which contains all possible trivial splits can be represented by a phylogenetic tree if and only if every pair of splits in ∑ is compatible.
18
19 ==== Hierarchy ====
20
21 A //hierarchy// is a set //H// of clusters in a set //X// so that for any pair of sets //A,B// in //H//, either //A// is a subset of //B//, //B// is a subset of //A//, or //A// and //B// are disjoint. Note that a hierarchy on //X// that contains all trivial clusters can always be represented by a rooted, phylogenetic tree (see e.g. Theorem 3.5.2 in Semple & Steel 2003).
22
23 ==== Split network ====
24
25 A //split network// on a set //X// is a special type of graph in which some subset of the vertices are labeled by elements of //X//, and certain collections of edges of the graph represent splits of //X//, just as the edges in a phylogenetic tree represent splits (see e.g. Section 4.3 in Huson et al. 2010). Split networks are often used to represent split systems which contain some pairs of incompatible splits, since such split systems cannot be represented in //any// phylogenetic tree (see above "compatible split systems").
26
27 Cf. also the entry [[set>>doc:stemmatology.Set.WebHome]].
28
29 ==== References ====
30
31 – Buneman, Peter. 1971. “The Recovery of Trees from Measures of Dissimilarity.” In //Mathematics in the Archaeological and Historical Sciences, //edited by Frank Roy Hodson, David George Kendall, and Petre Tautu, 387–385. Edinburgh: Edinburgh University Press.
32 – Semple, Charley, and Mike Steel. 2003.(% style="line-height: 1.4285715;" %)// Phylogenetics//(%%). Oxford: Oxford University Press.
33 – Huson, Daniel, Regula Rupp, and Celine Scornavacca. 2010. (% style="line-height: 1.4285715;" %)//Phylogenetic Networks. //(%%)Cambridge: Cambridge University Press.
34
35 ==== In other languages ====
36
37 English term used throughout
38
39
40 [[VM>>doc:stemmatology.Parvum lexicon stemmatologicum.Contributors.WebHome]], [[KH>>doc:stemmatology.Parvum lexicon stemmatologicum.Contributors.WebHome]]