models and algorithms: from the discrete to the continuous

Visit of Professor Zvavitch

May 2019 : Professor Zvavitch is visiting the Bézout LabEx, hosted by Matthieu Fradelizi (LAMA) for one month.

Professor Zvavitch is Professor at Kent State University. His main research interests are Convex Geometry, Geometric Functional Analysis, and applications of Probability and Harmonic Analysis to those subjects.

He will give a colloquium on June 11, 2019 at 11am in the Copernic building, room 4B107.

Title:  Can addition make things more convex?

Abstract: If $A$ and $B$ are sets in ${\mathbb R}^n$, then
$$A+B=\{a+b: a\in A, b\in B\}$$
is the   {\it Minkowski sum} of $A$ and $B$. It is not hard to see that if $A$ and $B$ are two convex sets then $A+B$ is also convex and $A+A=2A$, for a convex set $A$. Things become much less trivial if we would not assume that set $A$ is convex.  Indeed, in such a case $A+A$ is not necessary equal to $2A$. But there is a strong feeling that $2A$ become “more” convex than $A$.
More precisely, let us define for a compact set $A \subset {\mathbb R}^n$ the sequence
$$A(k) = \left\{\frac{a_1+\cdots +a_k}{k}: a_1, \ldots, a_k\in A\right\}=\frac{1}{k}\Big(\underset{k\ {\rm times}}{\underbrace{A + \cdots + A}}\Big).$$
It was  proved by Shapley, Folkman and Starr (1969) and by Emerson and Greenleaf (1969) that $A(k)$ approaches the convex hull of $A$ in the Hausdorff distance as $k$ goes to $\infty$.

The goal of this lecture  is to  explore how exactly $A(k)$ approaches the convex hull of $A$, as measured by various indices of non-convexity. In particular, we will present a conjecture proposed, a few years ago, by Bobkov, Madiman and Wang, that the volume of $A(k)$ is non-decreasing in $k$, or in other words, that when the volume deficit between the convex hull of $A$ and $A(k)$ goes to $0$, it actually does so monotonically.  For example, fixing $k=2$, is it true that
$$vol_n\left(\frac{A+A+A}{3}\right) \ge vol_n\left(\frac{A+A}{2}\right),$$
for all compact sets $A \subset {\mathbb R}^n$. While this conjecture holds true in dimension 1, we show that it fails in dimension $12$ or greater. For other indices of non-convexity, we will present several positive results, including a strong monotonicity of Schneiders index in general dimension, and eventual monotonicity of the Hausdorff distance and effective standard deviation.
Along the way we will demonstrate relations of our results to Combinatorial Discrepancy Theory and Information theory.

The talk is based on a joint works with Mokshay Madiman, Matthieu Fradelizi,  Arnaud Marsiglietti and Zsolt L\’angi.