Minimising the sum of projections of a finite set

DOI10.1007/S00454-018-9975-2MaRDI QIDQ1991096zbMATH OpenOpenAlexFDO

Authors Vsevolod F. Lev, Misha Rudnev

Publication date 30 October 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

isoperimetric problemLoomis-Whitney inequalityprojections

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Abstract: Consider the projections of a finite set $Asubset{R}^n$ onto the coordinate hyperplanes. How small can the sum of the sizes of these projections be, given the size of $A$? In a different form, this problem has been studied earlier in the context of edge-isoperimetric inequalities on graphs, and it is can be derived from the known results that there is a linear order on the set of $n$-tuples with non-negative integer coordinates, such that the sum in question is minimised for the initial segments with respect to this order. We present a new, self-contained and constructive proof, enabling us to obtain a stability result and establish algebraic properties of the smallest possible projection sum. We also solve the problem of minimising the sum of the sizes of the one-dimensional projections.

Recommendations

• scientific article; zbMATH DE number 3904618
• How Small Can the Mean Shadow of a Set Be?
• Projecting Difference Sets on the Positive Orthant
• Projections of antichains
• Inverse additive problems for Minkowski sumsets. I

Cites work

• A superadditivity and submultiplicativity property for cardinalities of sumsets
• An inequality related to the isoperimetric inequality
• Edge-isoperimetric inequalities in the grid
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• Reverse and dual Loomis-Whitney-type inequalities

Cited in

(3)

• Minimal Boolean sum and blending-type projections and extensions
• Hat guessing on books and windmills
• Projecting Difference Sets on the Positive Orthant

This page was built for publication: Minimising the sum of projections of a finite set

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