Graphs as geometric objects - Nathan Linial

Computer Science/Discrete Mathematics Seminar I

Topic: Graphs as geometric objects
Speaker: Nathan Linial
Affiliation: The Hebrew University
Date: July 25, 2022

It may seem quite obvious that graphs carry a lot of geometric structure. Don't we learn in algorithm classes how to solve all-pairs-shortest-paths, minimum spanning trees etc.? However, in this talk, I will try to impress on you the idea that there is much more to be discovered here. For example: Let G=(V,E) be a graph and let w be a mapping from E to the positive reals. Let us restrict ourselves to the case where no ties occur and so for every two distinct vertices u,v there is a unique w-shortest path that connects them (uniqueness holds with probability 1). Let w’ be another set of positive weights on E. We consider w and w’ equivalent if they define the same system of shortest paths. Question: Given a graph G how many such different equivalence classes can it have at least/at most? Also, we say that a path system on G is consistent if it is closed under taking subpaths. Question: Does every consistent path system on G come from a function w as above? The answer is an emphatic NO.

The new results are from joint work with my student Daniel Cizma.

Linial-2022-07-25