On the inequalities of projected volumes and the constructible region

DOI10.1137/18M1184679MaRDI QIDQ5376541zbMATH OpenOpenAlexWikidataFDO

Authors Zihan Tan, Li Wei Zeng

Publication date 13 May 2019

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

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

zbMATH Keywords

projectioninequalityconstructible region

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

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)