4
$\begingroup$

We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant in $(0,1)$).


Question: How can we prove or disprove that, for all convex $C\subseteq [0,1]^d$ and all $d\in\mathbb{N}$, there exists a set of $n$ points lying on the boundary of $C$ where $n$ grows at most polynomially in $d$, such that the volume of their convex hull $C'$ is lower bounded by a constant independent of $d$?



Note: The main intuition underlying this conjecture is the idea that (very) informally, for $d\gg 1$ if there are areas where the boundary of $C$ is far from being linear (e.g., portions of $(d-1)$-balls), the volume of the regions of $C$ bounded by such areas is disregardable compared to the volume of $C$. More generally, the same holds for areas formed by $\omega(\mathrm{poly}(d))$-many linear regions that can be viewed as good approximations of manifolds with significant curvature.

$\endgroup$
2
  • 3
    $\begingroup$ If $C$ is the cube $[0,\sqrt[d]{0.5}]^d$, what set of $n$ points can you find? I'm not seeing an obvious one. $\endgroup$ Sep 1, 2022 at 17:16
  • $\begingroup$ I see the point @RavenclawPrefect , thank you! Now, thinking about the original problem I am working on from which this subproblem arose, I would like to ask the same question where $n$ can be arbitrarely large (even superpolynomial in $d$), and the conjecture is instead that the number $\phi$ of facets of $C'\subseteq C$ (in place of its number of vertices $n$) grows at most polynomially in $d$, while the volume of $C'$ is still lower bounded by a constant independent of $d$. Do you see any potential counterexample for the conjecture in this case? $\endgroup$ Sep 1, 2022 at 18:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.