Minimising the Sum of Projections of a Finite Set

作者：Lev Vsevolod F^*; Rudnev Misha

来源：Discrete & Computational Geometry, 2018, 60(2): 493-511.

DOI：10.1007/s00454-018-9975-2

• Isoperimetric problem
• Loomis-Whitney inequality
• Projections

Consider the projections of a finite set 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 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.

• 出版日期2018-9