19. May 2026

Path Geometry

Vienna Combinatorics Seminar ( VCS)

Datum: 19. May 2026 | 15:00 – 18:00
Sprecher: Nati Linial, Hebrew University of Jerusalem
Veranstaltungsort: Raiffeisen Lecture Hall, Central Building
Sprache: Englisch

Abstract: 

Let X=[n] be a finite set of points. An (x,y)-path is a sequence of distinct points that starts with x and ends with y. A path system Π on X is a collection of paths with exactly one (x,y)-path for every two distinct points x,y∈X. Think of this path Px,y as the chosen path between these two points. We always assume that Py,x coincides with Px,y read in reverse. We say that the path system Π is consistent if the following holds: For every point z on the path Px,y, this path is the concatenation of the paths Px,z and Pz,y. It is easy to construct metric consistent path systems: Assign a positive distance w(u,v) with every pair of points u,v∈X and let Px,y be a w-shortest (x,y) path Q; Is every consistent path system necessarily metric? The answer is negative and we give various quantitative manifestations of this statement. Skipping the necessary definitions we ask if every consistent path system is approximately metric. A: there exist consistent path systems with metric distortion Ω(√n). The best result of this form is still unknown. I will briefly survey some of the many results that we already have in this general domain. Every path system gives rise to a graph (X,E) where xy is an edge whenever the path Px,y=x,y. Indeed, many of our results are graph-theoretic. All the papers in this domain are joint with my student Daniel Cizma, some are also with Maria Chudnovsky, if time allows I will also mention a recent result with my students Itai Goldflam.