Skip to main content

Juan M. Alonso: Graphs associated to finite metric spaces

Time: Tue 2022-04-12 10.15

Location: KTH, 3721, Lindstedtsvägen 25, and Zoom

Video link: Meeting ID: 659 3743 5667

Lecturer: Juan M. Alonso ((BIOS) IMASL - CONICET and Universidad Nacional de San Luis)


Many concrete problems are formulated in terms of a finite set of points in some \(\mathbb{R}^N\) which, via the ambient Euclidean metric, becomes a finite metric space \((M,d)\). This situation arises, for instance, when studying the glass transition from simulations.

To obtain information from M it is not always possible to use your favorite mathematical tool directly on M. The “favorite tool” in my case is finite dimension which, although defined on finite metric spaces, is not effectively computable when M is large and unstructured. In such cases, a useful alternative is to associate a graph to M, and do mathematics directly on the graph, rather than on the space. One should think of this graph as an approximation to M.

Among the many graphs that can be associated to M, I first considered \({MC} = {MC}(M)\), the Minimum Connected graph, a version — adapted to our situation — of the Vietoris complex of a metric space. Unfortunately MC is usually a rather dense graph. I then introduce \(CS = CS(M)\), the Connected Sparse graph, a streamlined version of MC. CS encodes the local information of M; in fact, it is almost a definition of what local structure of M means. 

Despite its name, CS can be dense, even a complete graph. However, in our application to glass, we computed CS for more than 700 spaces with about 2200 points each. All of them turned out to be trees. 

To understand this “coincidence”, I considered \(\mathfrak{M}_k\), the set of all subsets of k elements contained in some fixed \(\mathbb{R}^N\), and defined a metric on it. In the talk I will describe subsets D of \(\mathfrak{M}_k\) such that D contains open and dense subsets of \(\mathfrak{M}_k\), and have, moreover, the property that CS(M) is a tree for all M in D. In particular, the “general case” is for CS to be a tree.