The Generalized Makeev Problem Revisited

Abstract

Based on a result of Makeev, in 2012 Blagojević and Karasev proposed the following problem: given any positive integers $m$ and $1\le \ell \le k$, find the minimum dimension $d=\Delta (m;\ell /k)$ such that for any $m$ mass distributions on ${\mathbb{R}}^d$, there exist $k$ hyperplanes, any $\ell$ of which equipartition each mass. The $\ell =k$ case is a central question in geometric and topological combinatorics which remains open except for few values of $m$ and $k$. For $\ell <k$ and arbitrary $m$, we establish new upper bounds on $\Delta (m;\ell /k)$ when (1) $\ell =2$ and $k$ is arbitrary and (2) $\ell =3$ and $k=4$. When $\ell =k-1$ and $m+1$ is a power of two these bounds are nearly optimal and are exponentially smaller than the current best upper bounds when $\ell =k$. Similar remarks apply to our upper bounds when the hyperplanes are prescribed to be pairwise orthogonal. Lastly, we provide transversal extensions of our results along the lines recently established by Frick et al.: given $m$ families of compact convex sets in ${\mathbb{R}}^d$ such that no $2^{\ell }$ members of any family are pairwise disjoint, we show that every member of each family is pierced by the union of any $\ell$ of some collection of $k$ hyperplanes.

17 pages. Final version, corrects typos

References in corpus (1)

• Transversal generalizations of hyperplane equipartitions