Minimising the Sum of Projections of a Finite Set

Vsevolod F. Lev*, Misha Rudnev

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

121 Downloads (Pure)

Abstract

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

Original languageEnglish
Pages (from-to)493-511
Number of pages19
JournalDiscrete and Computational Geometry
Volume60
Issue number2
Early online date8 Mar 2018
DOIs
Publication statusPublished - Sep 2018

Keywords

  • Isoperimetric problem
  • Loomis–Whitney inequality
  • Projections

Fingerprint Dive into the research topics of 'Minimising the Sum of Projections of a Finite Set'. Together they form a unique fingerprint.

Cite this