Combinatorics Seminar 2015

Speaker: Zeying Xu (徐泽瀛), Shanghai Jiao Tong University

Date: Tue, Dec 01, 2015

Time: 15:00 - 15:50

Venue: Middle Meeting Room

Title: Polyhedral representations of finite metric spaces: Tight span and Kantorovich-Rubinstein norm


This talk is about two polyhedral representations of finite metric spaces. The first is the tight span of a metric, invented by Isbell with the name "injective hull" and rediscovered by Dress to represent phylogenetic network. The second is the unit ball of the Kantorovich-Rubinstein norm associated to a metric, which is a concept arising from transportation problem.

Tight span is widely used in biology to study evolution. Not only its geometric structure is beautiful, but also its canonical metric decomposition is fascinating.

The unit ball of the Kantorovich-Rubinstein norm is a polytope. The combinatorial structures of this polytope shed light into both the properties of the norm and the properties of the metric itself. Vershik posed the open problem of characterizing the combinatorial structures of this unit ball.

In an ongoing joint work with Yaokun Wu, we are trying to reveal the connections between these two polyhedral representations of finite metrics.


[1] A.W.M. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces, Advances in Mathematics, 53 (1984) 321--402.

[2] J.R. Isbell, Six theorems about injective metric spaces, Commentarii Mathematici Helvetici, 39 (1964) 65--76.

[3] L.V. Kantorovich, G.Sh. Rubinshtein, On a space of totally additive functions, Vestn. Leningrad. Univ, 13 (1958) 52--59 (in Russian).

[4] A.M. Vershik, Classification of finite metric spaces and combinatorics of convex polytopes, Arnold Mathematical Journal, 1 (2015) 75--81.

[5] A.M. Vershik, Long history of the Monge-Kantorovich transportation problem, The Mathematical Intelligencer, 35 (2013) 1--9.