Date: Fri, 1 Dec 2023 17:47:44 +0200 (EET) Message-ID: <368904572.12886.1701445664090@wiki-1.it.helsinki.fi> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_12885_2068579483.1701445664090" ------=_Part_12885_2068579483.1701445664090 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Split

# Split

A split can be thought of a division of a set into two disjoint subsets. More precisely, a split = of a set X is a partition of X into two, non-empty, disjo= int 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, Russ= ian, 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 whic= h A and B are listed does not matter). Using this notatio= n, the split above becomes {French, English} | {Chinese, Russian, Italian}.=

#### Trivial split

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}.

#### Split system

A split system =E2=88=91 on a set X is a set of splits= of X. For example, { {French, English} | {German, Italian}, {Fren= ch, German} | {English, Italian} }, is a split system on the set {French, E= nglish, German, Italian}, that contains two splits.

#### Compatible splits (in= compatible splits)

Two distinct splits A|B and C|D of a= set are called compatible if one of the intersections A = =E2=88=A9 C, A =E2=88=A9 D, B =E2=88=A9= C, and B =E2=88=A9 D is empty. Two splits are c= alled incompatible if they are not compatible. Note that in a phylogenetic tree with = leaf set X, each of the= edges induces a split of X<= /em>, and that the two splits induced by any pair of distinct edges in the = tree are compatible.

#### Compatible split system

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 contain= s all possible trivial splits can always be represented by a (unique) phylo= genetic tree with leaf set X (see e.g. Theorem 3.1.4 ). In part= icular, 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 =E2=88=91 which contains = all possible trivial splits can be represented by a phylogenetic tree if an= d only if every pair of splits in =E2=88=91 is compatible.

#### Hierarchy

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<= /em> and B are disjoint. Note that a hierarchy on X that = contains all trivial clusters can always be represented by a rooted, phylog= enetic tree (see e.g. Theorem 3.5.2 in Semple & Steel 2003).

#### Split network

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. Sec= tion 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 s= plit systems cannot be represented in any phylogenetic tree (see a= bove "compatible split systems").

Cf. also the entry set.

#### References

=E2=80=93 Buneman, Peter. 1971. =E2=80=9CThe Recovery of Trees from Meas= ures of Dissimilarity.=E2=80=9D In Mathematics in the Archaeological an= d Historical Sciences, edited by Frank Roy Hodson, David Geo= rge Kendall, and Petre Tautu, 387=E2=80=93385. Edinburgh: Edinburgh Un= iversity Press.
=E2=80=93 Semple, Charley, and Mike Steel. 2003. Phylogenetics. Oxford: Oxford University Press.
=E2=80=93 Huson, Daniel, Regula Rupp, and Celine Scornavacca. 2010. Phylogenetic Networks. Cambridge: = Cambridge University Press.

#### In other languages

English term used throughout

VM, KH

------=_Part_12885_2068579483.1701445664090--