Isoperimetry in integer lattices

Ben Barber; Joshua Erde

doi:10.19086/da.3555

Isoperimetry in integer lattices

Ben Barber, Joshua Erde

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

6 Citations (Scopus)

392 Downloads (Pure)

Abstract

The edge isoperimetric problem for a graph G is to determine, for each n, the minimum number of edges leaving any set of n vertices. In general this problem is NP-hard, but exact solutions are known in some special cases, for example when G is the usual integer lattice. We solve the edge isoperimetric problem asymptotically for every Cayley graph on Z^d. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.

Original language	English
Article number	3555
Number of pages	16
Journal	Discrete Analysis
Volume	7
DOIs	https://doi.org/10.19086/da.3555
Publication status	Published - 20 Apr 2018

Access to Document

10.19086/da.3555

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via Diamond OA Journals at http://discreteanalysisjournal.com/article/3555-isoperimetry-in-integer-lattices . Please refer to any applicable terms of use of the publisher.
Final published version, 295 KBLicence: CC BY

Handle.net

Persistent link

Cite this

@article{2464a63cf19141ecbe6fc0a67c1b8d25,

title = "Isoperimetry in integer lattices",

abstract = "The edge isoperimetric problem for a graph G is to determine, for each n, the minimum number of edges leaving any set of n vertices. In general this problem is NP-hard, but exact solutions are known in some special cases, for example when G is the usual integer lattice. We solve the edge isoperimetric problem asymptotically for every Cayley graph on Zd. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.",

author = "Ben Barber and Joshua Erde",

year = "2018",

month = apr,

day = "20",

doi = "10.19086/da.3555",

language = "English",

volume = "7",

journal = "Discrete Analysis",

issn = "2397-3129",

publisher = "Alliance of Diamond OA Journals",

}

TY - JOUR

T1 - Isoperimetry in integer lattices

AU - Barber, Ben

AU - Erde, Joshua

PY - 2018/4/20

Y1 - 2018/4/20

N2 - The edge isoperimetric problem for a graph G is to determine, for each n, the minimum number of edges leaving any set of n vertices. In general this problem is NP-hard, but exact solutions are known in some special cases, for example when G is the usual integer lattice. We solve the edge isoperimetric problem asymptotically for every Cayley graph on Zd. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.

AB - The edge isoperimetric problem for a graph G is to determine, for each n, the minimum number of edges leaving any set of n vertices. In general this problem is NP-hard, but exact solutions are known in some special cases, for example when G is the usual integer lattice. We solve the edge isoperimetric problem asymptotically for every Cayley graph on Zd. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.

UR - https://arxiv.org/abs/1707.04411v2

U2 - 10.19086/da.3555

DO - 10.19086/da.3555

M3 - Article (Academic Journal)

SN - 2397-3129

VL - 7

JO - Discrete Analysis

JF - Discrete Analysis

M1 - 3555

ER -

Isoperimetry in integer lattices

Abstract

Access to Document

Handle.net

Other files and links

Embargoed Document

Fingerprint

Cite this