10/5/2021 Combinatorics, Physics and Probability Seminar

2021-10-05 09:00 - 10:00

Title: Geodesic Geometry on Graphs

Abstract: 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.