Annals of Combinatorics 1 (1997) 339-352

Some Variations on a Theme by Buneman

A. Dress, K. Huber, and V. Moulton

FSPM-Strukturbildugsprozesse, University of Bielefeld, Bielefeld, D-33501, Germany
{dress, khuber, moulton}

Received October 14, 1997

AMS Subject Classification: 04A03, 04A20, 05C99, 52B99, 92B99

Abstract. In 1971, Peter Buneman presented a paper in which he described, amongst other things, a way to construct a tree from a collection of pairwise compatible splits of a finite set. This construction is immediately generalizable to a collection of arbitrary splits, in which case it gives rise to the Buneman graph, a certain connected, median graph representing the given collection of splits in a canonical fashion. In this paper, we look at the complex obtained by filling those faces of the associated hypercube whose vertices consist only of vertices in the Buneman graph, a complex that we call the Buneman complex. In particular, we give a natural filtration of the Buneman complex, and show that this filtration collapses when the system of splits is weakly compatible. In the case where the family of splits is not weakly compatible, we also see that the filtration naturally gives us a way to associate a graded hierarchy of phylogenetic networks to the collection of splits.

Keywords: phylogenetic networks, phylogenetic trees, median networks, hypercubes, hierarchical clustering, split systems, split decomposition, Buneman graphs, compatibilty of Taxonomic characters


1.  H.-J. Bandelt, Phylogenetic networks, Verh. naturwiss. Ver. Hamburg 34 (1991) 51–57.

2.  H.-J. Bandelt and A. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47–105.

3.  H.-J. Bandelt and A. Dress, A new and useful approach to phylogenetic analysis of distance data, Molecular Phylogenetics and Evolution 1 (1992) 242–252.

4.  H.-J. Bandelt and A. Dress, A relational approach to split decomposition, In: Information and Classification, O. Opitz et al., Eds., Springer-Verlag, 1993, pp. 123–131.

5.  P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archeological and Historical Sciences, F.~Hodson et al., Eds., Edinburgh University Press, 1971, pp. 387–395.

6.  J. Barthelemy, From copair hypergraphs to median graphs with latent vertices, Discrete Math. 76 (1989) 9–28.

7.  J. Barthelemy and A. Guenoche, Trees and Proximity Representations, John Wiley, 1991.

8.  A. Dress, M. Hendy, K. Huber, and V. Moulton, On the number of vertices and edges of the Buneman graph, Ann. Combin. 1 (1997) 329–337.

9.  A. Dress, K. Huber, and V. Moulton, A new characterization of weak compatibility using the T-construction, in preparation.

10.  A. Dress, D. Huson, and V. Moulton, Analyzing and visualizing distance data with the splits-tree graph, Discrete Appl. Math. 71 (1996) 95–110.

11.  A. Dress, V. Moulton, and W. Terhalle, T-theory: an overview, Europ. J. Combin. 17 (1996) 161–175.

Get the LaTex | DVI | PS file of this abstract.