The metric geometry of subsets of the Hamming cube

Abstract:

All the distance data for a finite metric spaces $X = \{x_1,\dots,x_n\}$ is stored in its distance matrix $D = (d(x_i,x_j))_{i,j=1}^n$. A common theme in distance geometry is to try to link linear algebraic properties of this matrix with more geometric properties, such as whether you can isometrically embed $X$ into Euclidean space (or perhaps some other nice space).

Two much-studied classes of finite metric spaces are trees with the path metric, and spaces formed by taking collections of bit-strings of length $n$ and applying the Hamming metric. The distance matrices for such spaces have some quite surprising properties. In this talk we shall start by introducing Graham and Pollak's 1971 formula for the determinant of the distance matrices of tree, and progress to some much more recent formulas. No special knowledge beyond second year linear algebra will be assumed!

This is joint work with Gavin Robertson, Alan Stoneham, Tony Weston and Reihard Wolf.