Minimising the Sum of Projections of a Finite Set

Vsevolod F. Lev; Misha Rudnev

doi:10.1007/s00454-018-9975-2

Minimising the Sum of Projections of a Finite Set

Vsevolod F. Lev^*, Misha Rudnev

^*Corresponding author for this work

Research output: Contribution to journal › Article (Academic Journal) › peer-review

1 Citation (Scopus)

129 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 language	English
Pages (from-to)	493-511
Number of pages	19
Journal	Discrete and Computational Geometry
Volume	60
Issue number	2
Early online date	8 Mar 2018
DOIs	https://doi.org/10.1007/s00454-018-9975-2
Publication status	Published - Sept 2018

Keywords

Isoperimetric problem
Loomis–Whitney inequality
Projections

Access to Document

10.1007/s00454-018-9975-2

Full-text PDF (accepted author manuscript)
This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Springer at https://link.springer.com/article/10.1007%2Fs00454-018-9975-2 . Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 215 KBLicence: Other

Handle.net

Persistent link

Cite this

@article{31ada0dfb8054df3945b3597f4ca2bfb,

title = "Minimising the Sum of Projections of a Finite Set",

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.",

keywords = "Isoperimetric problem, Loomis–Whitney inequality, Projections",

author = "Lev, {Vsevolod F.} and Misha Rudnev",

year = "2018",

month = sep,

doi = "10.1007/s00454-018-9975-2",

language = "English",

volume = "60",

pages = "493--511",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer, New York, NY",

number = "2",

}

TY - JOUR

T1 - Minimising the Sum of Projections of a Finite Set

AU - Lev, Vsevolod F.

AU - Rudnev, Misha

PY - 2018/9

Y1 - 2018/9

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

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

KW - Isoperimetric problem

KW - Loomis–Whitney inequality

KW - Projections

UR - http://www.scopus.com/inward/record.url?scp=85043360010&partnerID=8YFLogxK

UR - https://arxiv.org/abs/1610.02504

U2 - 10.1007/s00454-018-9975-2

DO - 10.1007/s00454-018-9975-2

M3 - Article (Academic Journal)

AN - SCOPUS:85043360010

SN - 0179-5376

VL - 60

SP - 493

EP - 511

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

Minimising the Sum of Projections of a Finite Set

Abstract

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this