Combinatorics Seminar

Let P be a system of unique shortest paths through a graph with real edge weights. A well-known fact is that P must be "consistent," meaning that no two of these paths can intersect each other, split apart, and then intersect again later. But is that all the guaranteed structure? Can any consistent path system be realized as unique shortest paths in some graph? Or are there more forbidden combinatorial intersection patterns that can be found?

In this talk, we will complete the list of forbidden intersection patterns for systems of unique shortest paths, characterizing the set of unique shortest path systems via forbidden patterns. We will then say a little about some connections between graph metrics and topology that enable our characterization theorem.
Speaker(s): Gregory Bodwin (University of Michigan)