Isoperimetry in integer lattices

Ben Barber, Joshua Erde

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

239 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 Zd. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.
Original languageEnglish
Article number3555
Number of pages16
JournalDiscrete Analysis
Volume7
DOIs
Publication statusPublished - 20 Apr 2018

Fingerprint

Dive into the research topics of 'Isoperimetry in integer lattices'. Together they form a unique fingerprint.

Cite this