Talks Spring 2021

A Spectral Approach to Polytope Diameter - Part 2

Saturday, April 10th, 2021, 2:05 pm2:30 pm

Add to Calendar

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.