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
Смотрите видео Graphs as geometric objects - Nathan Linial онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Institute for Advanced Study 25 Июль 2022, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 3,541 раз и оно понравилось 117 людям.