When: Sunday, May 9, 10am
Where: Schreiber 309
Speaker: Daniel Cizma, Hebrew
University
Title:
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 path $P_{u,v}$ in $S$ which connects them. The path system is said to be consistent if for every path $P_{u,v}$ in $S$ and vertices $x,y$ in $P_{u,v}$ the $xy$ subpath of $P_{u,v}$ coincides with $P_{x,y}$. A metric $d$ on $G$ is said to induce $S$ if every path in $S$ is shortest with respect to $d$. Our focus is on the following question: Which graphs $G$ have the property that every consistent path system in $G$ is induced by some such $d$? We say graphs with this property are metrizable. In this talk, we will discuss the notion of graph metrizability. In particular, we will see that while metrizability is a rare property, there exists infinitely many $2$-connected metrizable graphs.
Joint work with Nati Linial. https://arxiv.org/abs/2007.13782, to appear in Discrete Comput. Geom.