On the Inequalities of Projected Volumes and the Constructible Region

Abstract

We study the following geometry problem: given a $2^n-1$ dimensional vector $\pi =\{{\pi }_S{\}}_{S\subseteq [n],S\ne \varnothing }$, is there an object $T\subseteq {\mathbb{R}}^n$ such that $\log (\mathsf{vol}(T_S))={\pi }_S$, for all $S\subseteq [n]$, where $T_S$ is the projection of $T$ to the subspace spanned by the axes in $S$? If $\pi$ does correspond to an object in ${\mathbb{R}}^n$, we say that $\pi$ is {\em constructible}. We use ${\Psi }_n$ to denote the constructible region, i.e., the set of all constructible vectors in ${\mathbb{R}}^{2^n-1}$. In 1995, Bollobás and Thomason showed that ${\Psi }_n$ is contained in a polyhedral cone, defined a class of so called uniform cover inequalities. We propose a new set of natural inequalities, called nonuniform-cover inequalities, which generalize the BT inequalities. We show that any linear inequality that all points in ${\Psi }_n$ satisfy must be a nonuniform-cover inequality. Based on this result and an example by Bollobás and Thomason, we show that constructible region ${\Psi }_n$ is not even convex, and thus cannot be fully characterized by linear inequalities. We further show that some subclasses of the nonuniform-cover inequalities are not correct by various combinatorial constructions, which refutes a previous conjecture about ${\Psi }_n$. Finally, we conclude with an interesting conjecture regarding the convex hull of ${\Psi }_n$.