Skip to Content

Search: {{$root.lsaSearchQuery.q}}, Page {{$root.page}}

Combinatorics Seminar

On the structure of unique shortest paths in graphs
Friday, January 29, 2021
3:00-4:00 PM
Off Campus Location
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)
Building: Off Campus Location
Location: Virtual
Event Type: Workshop / Seminar
Tags: Mathematics
Source: Happening @ Michigan from Department of Mathematics