Graphs as geometric objects
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.