CMSA Combinatorics, Physics and Probability Seminar: Geodesic Geometry on Graphs
Daniel Cizma - Hebrew University of Jerusalem
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.