On the inequalities of projected volumes and the constructible region

DOI10.1137/18M1184679zbMATH Open1411.05252arXiv1410.8663OpenAlexW2962832166WikidataQ127959106 ScholiaQ127959106MaRDI QIDQ5376541FDOQ5376541

Authors: Zihan Tan, Li Wei Zeng 

Publication date: 13 May 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We study the following geometry problem: given a $2^n-1$ dimensional vector $pi={p{i}_S}_{Ssubseteq[n],Seemptyset}$, is there an object $Tsubseteqmathbb{R}^n$ such that $log(mathsfvol(T_S))=p{i}_S$, for all $Ssubseteq[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 $Ps{i}_n$ to denote the constructible region, i.e., the set of all constructible vectors in $mathbb{R}^{2^n-1}$. In 1995, Bollob'{a}s and Thomason showed that $Ps{i}_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 $Ps{i}_n$ satisfy must be a nonuniform-cover inequality. Based on this result and an example by Bollob'{a}s and Thomason, we show that constructible region $Ps{i}_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 $Ps{i}_n$. Finally, we conclude with an interesting conjecture regarding the convex hull of $Ps{i}_n$.

Full work available at URL: https://arxiv.org/abs/1410.8663

Recommendations

• Inequalities on Projected Volumes
• Covering shadows with a smaller volume
• Volume bounds for shadow covering
• Uniform cover inequalities for the volume of coordinate sections and projections of convex bodies
• Restricted chord projection and affine inequalities

zbMATH Keywords

projectioninequalityconstructible region

Mathematics Subject Classification ID

Extremal set theory (05D05) Inequalities and extremum problems in real or complex geometry (51M16)

Cites Work

• Combinatorial optimization. Theory and algorithms.
• Projections of Bodies and Hereditary Properties of Hypergraphs
• An inequality related to the isoperimetric inequality
• Some intersection theorems for ordered sets and graphs
• Hypergraphs, entropy, and inequalities
• Information theory and network coding
• A new class of non-Shannon-type inequalities for entropies
• A non-Shannon-type conditional inequality of information quantities
• Projections, entropy and sumsets

Cited In (2)

• Inequalities on Projected Volumes
• Erratum to: ``On the inequalities of projected volumes and the constructible region

This page was built for publication: On the inequalities of projected volumes and the constructible region

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5376541)