Quantitative Helly-type theorems via sparse approximation

Matthew Kendall, Princeton University

Date and time: 6pm (New York time), Tuesday, September 20, 2022

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

We may be able to offer this talk on Zoom as well. Details TBA.

Working on a topic whose research was initiated by Bárány, Katchalski, and Pach in 1982, we study quantitative Helly-type theorems for the volume and the diameter of convex sets. We prove the following sparse approximation result for polytopes. Assume that $Q$ is a polytope in John's position. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q'$ satisfies $Q \subset - 2d^2 Q'$. As a consequence, we retrieve the best bound for the quantitative Helly-type result for the volume, achieved by Brazitikos, and improve on the strongest bound for the quantitative Helly-type theorem for the diameter, shown by Ivanov and Naszódi: We prove that given a finite family $F$ of convex bodies in $\mathbb{R}^d$ with intersection $K$, we may select at most $2d$ members of F such that their intersection has volume at most $(cd)^{3d/2} \mathop{\mathrm{vol}} K$, and it has diameter at most $2 d^2 \mathop{\mathrm{diam}} K$, for some absolute constant $c > 0$.

This is joint work with Víctor Hugo Almendra-Hernández and Gergely Ambrus.