Talks
Spring 2021
A Spectral Approach to Polytope Diameter - Part 2
Saturday, April 10th, 2021, 2:05 pm–2:30 pm
Speaker:
Nikhil Srivastava (University of California, Berkeley)
A classic question in discrete geometry is: what is the maximum possible diameter of the skeleton of a polytope P ={x\in R^d: Ax\le b} in $R^d$ defined by $m$ constraints, as a function of $m$ and $d$? We describe a new approach to this problem which uses classical inequalities from convex geometry to bound the eigenvalues of a certain weighted adjacency matrix of the skeleton, thereby yielding an upper bound in terms of $m, d$ and some quantities depending on the polar of the $P$. Joint work with H. Narayanan and R. Shah.