Isoperimetry in integer lattices

DOI10.19086/DA.3555MaRDI QIDQ4645032zbMATH OpenOpenAlexWikidataFDO

Authors Ben Barber, Joshua Erde

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1707.04411

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Infinite graphs (05C63)

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 $mathbb{Z}^d$. The near-optimal shapes that we exhibit are zonotopes generated by line segments corresponding to the generators of the Cayley graph.

Recommendations

• A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
• The edge-isoperimetric problem on the 600-vertex regular solid
• scientific article; zbMATH DE number 2188353
• \(N^{3/4}\) law in the cubic lattice
• Edge-isoperimetric problems for Cartesian powers of regular graphs

Cites work

• A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
• A note on the edges of the n-cube
• Almost isoperimetric subsets of the discrete cube
• An inequality related to the isoperimetric inequality
• Approximating the Permanent
• Assignment of Numbers to Vertices
• Compressions and isoperimetric inequalities
• Computing the Continuous Discretely
• Discrete Isoperimetric Problems
• Edge-isoperimetric inequalities in the grid
• Eine zahlentheoretische Anwendung der Graphentheorie.
• Erdös distance problems in normed spaces
• Expander codes
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 881168 (Why is no real title available?)
• Maximally Connected Arrays on the n-Cube
• On an isoperimetric problem for Hamming graphs
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs
• Some simplified NP-complete graph problems
• Stability results for the Brunn-Minkowski inequality
• Vertex Bisection is Hard, too
• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)

Cited in

(20)

• The edge-isoperimetric problem on the 600-vertex regular solid
• The edge-isoperimetric problem for discrete tori
• Isoperimetric theorems in the binary sequences of finite lengths
• Similarity isometries of shifted lattices and point packings
• \(N^{3/4}\) law in the cubic lattice
• The number of rectangular islands by means of distributive lattices
• Symmetry breaking in two-dimensional square grids: persistence and failure of the dimensional crossover
• On a characterization of lattice cubes via discrete isoperimetric inequalities
• A Brunn-Minkowski inequality for the integer lattice
• scientific article; zbMATH DE number 417976 (Why is no real title available?)
• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
• scientific article; zbMATH DE number 861335 (Why is no real title available?)
• A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
• Indices of coincidence isometries of the hypercubic lattice {\bb Z}^{n}
• scientific article; zbMATH DE number 2188353 (Why is no real title available?)
• Isoperimetric stability in lattices
• An extremal graph problem on a grid and an isoperimetric problem for polyominoes
• Sharp \(N^{3/4}\) law for the minimizers of the edge-isoperimetric problem on the triangular lattice
• Isoperimetric stability in lattices (extended abstract)
• Planar lattice subsets with minimal vertex boundary

This page was built for publication: Isoperimetry in integer lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645032)