CMSA Combinatorics, Physics and Probability Seminar: Geodesic Geometry on Graphs

In a graph G = (V, E) we consider a system of paths S so that for every two vertices u,v in V there is a unique uv path in S connecting them. The path system is said to be consistent if it is closed under taking subpaths, i.e. if P is a path in S then any subpath of P is also in S. Every positive weight function w: E–>R^+ gives rise to a consistent path system in G by taking the paths in S to be geodesics w.r.t. w. In this case, we say w induces S. We say a graph G is metrizable if every consistent path system in G is induced by some such w.

We’ll discuss the concept of graph metrizability, and, in particular, we’ll see that while metrizability is a rare property, there exists infinitely many 2-connected metrizable graphs.

Joint work with Nati Linial.

Zoom link: https://harvard.zoom.us/j/99715031954?pwd=eVRvbERvUWtOWU9Vc3M2bjN3VndBQT09

Password: 1251442