skip to content

Optimal and hereditarily optimal realisation of metric spaces

Friday 7th September 2007 - 10:20 to 10:40
INI Seminar Room 1

Given a finite set X and a metric d on X, a realization of (X,d) is a weighted graph G=(V,E,w) such that X is a subset of V and the distance d(x,y) between any pair of elements in X is the shortest distance between x and y in G. A realization such that the total edge weight of G is minimal is known as an optimal realization. It is well-known that if there exists a tree which is a realization of (X,d) then this tree is the unique optimal realization. In general however, optimal realizations are not trees, not necessarily unique, and notoriously hard to find. It has been suggested by Andreas Dress that optimal realizations may be possible to find by deleting edges in a larger graph known as the hereditarily optimal realization of the given metric, which is unique and can be explicitly calculated. Both optimal and hereditarily optimal realizations can be useful concepts in phylogenetics, especially when studying e.g. plants or viruses, where a phylogenetic tree is not necessarily the best representation of the evolutionary relationships.

We will outline some recent progress on this problem, showing both that optimal realizations can be found within hereditarily optimal realizations for all metrics on less than five elements, but also that there exist counterexamples, which in turn give rise to new questions.

Related Links

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons