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
Watch video Graphs as geometric objects - Nathan Linial online without registration, duration hours minute second in high quality. This video was added by user Institute for Advanced Study 25 July 2022, don't forget to share it with your friends and acquaintances, it has been viewed on our site 3,541 once and liked it 117 people.