MATH Seminar

Title: On The Structure of Unique Shortest Paths in Graphs
Seminar: Combinatorics
Speaker: Greg Bodwin of The Georgia Institute of Technology
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2019-01-28 at 4:00PM
Venue: MSC E408
Download Flyer
Abstract: Let P be a system of unique shortest paths through a graph with real edge weights (i.e. a finite metric). An obvious fact is that P is "consistent," meaning that no two of these paths can intersect each other, split apart, and then intersect again later. But is that all? Can any consistent path system be realized as unique shortest paths in some graph? Or are there more forbidden combinatorial intersection patterns out there to be found?\\ \\ In this talk, we will characterize exactly which path systems can or can't be realized as unique shortest paths in some graph by giving a complete list of new forbidden intersection patterns. Our characterization theorem is based on a new connection between graph metrics and certain boundary operators used in some recent graph homology theories. This connection also leads to a principled topological understanding of some of the popular algebraic tricks currently used in the literature on shortest paths.