Loading Events

« All Events

  • This event has passed.

10/5/2021 Combinatorics, Physics and Probability Seminar

October 5, 2021 @ 9:00 am - 10:00 am

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.


October 5, 2021
9:00 am - 10:00 am
Event Category: