Computer Science/Discrete Mathematics Seminar I

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.