Phylogenetic questions inspired by the theorems of Arrow and Dilworth

Biologists frequently need to reconcile conflicting estimates of the evolutionary relationships between species by taking a ‘consensus’ of a set of phylogenetic trees. This is because different data and/or different methods can produce different trees. If we think of each tree as providing a ‘vote’ for the unknown true phylogeny, then we can view consensus methods as a type of voting procedure. Kenneth Arrow’s celebrated ‘impossibility theorem’ (1950) shows that no voting procedure can simultaneously satisfy seemingly innocent and desirable properties. We consider a similar axiomatic approach to consensus and asks what properties can be jointly achieved.

In the second part of the talk, we consider phylogenetic networks (which are more general than trees as they allow for reticulate evolution). The question ‘when is a phylogenetic network merely a tree with additional links between its edges?’ is relevant to biology and interesting mathematically. It has recently been shown that such ‘tree-based’ networks can be efficiently characterized. We describe some further results related to Dilworth’s theorem for posets (1950), and matching theory in bipartite graphs. In this way, one can obtain fast algorithms for determining when a network is tree-based and, if not, to calculate how ‘close’ to tree-based it is.