Abstract: In this talk, we will explore a surprising connection between graph theory and convex geometry. We look at graphs whose edge weights are linear forms in $d$ variables. That is, the weight of each edge $e$ is given by $w_e (\lambda_1, \lambda_2, \ldots, \lambda_d) = a_{e,1} \lambda_1 + a_{e,2} \lambda_2 + \cdots + a_{e,d} \lambda_d$.
In the first part of this talk, Kshitij will show how the different shortest paths in such a graph (for different values of $\lambda_1, \lambda_2, \ldots, \lambda_d$) can be thought of as the extreme points of a polytope in $d$ dimensions.
In the second part of this talk, Prerona will explain how to upper bound the number of extreme points in such polytopes. If time permits, she will show that improving this result can help solve some questions in algebraic circuit complexity.
This is based on joint work with Jaikumar Radhakrishnan and Vaishali Surianarayanan.
