A sharp nonconvexity bound for partition ranges of vector measures with atoms (Q1300041)

The partition range of a vector measure \(\underline\mu=(\mu_1,\dots,\mu_n)\) on a measurable space \((\Omega, {\mathcal F})\) is the subset of \({\mathbb R}^n\) given by \(R(\underline\mu)=\{(\mu_1(A_1),\dots, \mu_n(A_n)):(A_1,\dots, A_n)\) is a measurable partition of \(\Omega\}\). If each \(\mu_i\) is atomless, a result of \textit{A.~Dvoretzky, A.~Wald} and \textit{J.~Wolfowitz} [Pac. J. Math. 1, 59-74 (1951; Zbl 0044.15002)] says that \(R(\underline\mu)\) is convex and compact (a generalization of Lyapounov's Convexity Theorem). The main result in this article is a sharp upper bound for the degree of nonconvexity of \(R(\underline\mu)\) as a function of the maximum (one-dimensional) mass of the atoms of \(\underline\mu\); namely, that the Hausdorff distance (with respect to the sup norm) from \(R(\underline\mu)\) to its convex hull is at most \(\alpha (n-1)/n\), where \(\alpha\) is the size of the largest atom. This bound improves on a result in [\textit{T. P. Hill} and \textit{Y.~Tong}, Ann. Stat. 17, No. 3, 1325-1334 (1989; Zbl 0683.62036)] by an order of magnitude \(\sqrt n\). The proof is deep, and uses ideas from graph theory, combinatorics, convex geometry (Shapley-Folkman lemma), univariate optimization, and a key proportionality equation (Lemma~3.6). The main inequality is a natural generalization of the convexity theorems of Lyapounov, and of Dvoretzky, Wald and Wolfowitz, and applications to fair division problems are given, as well as generalizations, to the case of measures with atoms, of several optimal-partitioning inequalities.