Date
Tue, 04 Nov 2025
Time
14:00 - 15:00
Location
L4
Speaker
Nati Linial
Organisation
Hebrew University of Jerusalem

Even in a totally discrete space $X$ you need to know how to move between distinct points. A path $P_{x,y}$ between two points $x,y \in X$ is a sequence of points in $X$ that starts with $x$ and ends with $y$. A path system is a collection of paths $P_{x,y}$, one per each pair of distinct points $x, y$ in $X$. We restrict ourselves to the undirected case where $P_{y,x}$ is $P_{x,y}$ in reverse.

Strictly metrical path systems are ubiquitous. They are defined as follows: There is some spanning, connected graph $(X, E)$ with positive edge weights $w(e)$ for all $e\in E$ and $P_{x,y}$ is the unique $w$-shortest $xy$ path. A metrical path system is defined likewise, but $w$-shortest paths need not be unique. Even more generally, a path system is called consistent  (no $w$ is involved here) if it satisfies the condition that when point $z$ is in $P_{x,y}$, then $P_{x,y}$ is $P_{x,z}$ concatenated with $P_{z,y}$. These three categories of path systems are quite different from each other and in our work we find quantitative ways to capture these differences.

Joint work with Daniel Cizma.

Last updated on 2 Nov 2025, 8:30pm. Please contact us with feedback and comments about this page.