A general method to determine limiting optimal shapes for edge-isoperimetric inequalities

MaRDI QIDQ510340zbMATHFDO

Authors Ellen Veomett, E. Tsukerman

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

latticesinfinite graphscontinuous isoperimetric problemdiscrete isoperimetric problem

Mathematics Subject Classification ID

Distance in graphs (05C12) Infinite graphs (05C63)

Abstract: For a general family of graphs on $mathbb{Z}^n$, we translate the edge-isoperimetric problem into a continuous isoperimetric problem in $mathbb{R}^n$. We then solve the continuous isoperimetric problem using the Brunn-Minkowski inequality and Minkowski's theorem on Mixed Volumes. This translation allows us to conclude, under a reasonable assumption about the discrete problem, that the shapes of the optimal sets in the discrete problem approach the shape of the optimal set in the continuous problem as the size of the set grows. The solution is the zonotope defined as the Minkowski sum of the edges of the original graph. We demonstrate the efficacy of this method by revisiting some previously solved classical edge-isoperimetric problems. We then apply our method to some discrete isoperimetric problems which had not previously been solved. The complexity of those solutions suggest that it would be quite difficult to find them using discrete methods only.

Recommendations

• scientific article; zbMATH DE number 2060183
• Isoperimetry in integer lattices
• General edge-isoperimetric inequalities. I: Information-theoretical methods
• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
• The edge-isoperimetric problem on the 600-vertex regular solid

Cites work

• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 3048077 (Why is no real title available?)
• An Isoperimetric Inequality on the Discrete Torus
• An Ordering on the Even Discrete Torus
• An inequality for functions on the Hamming cube
• Assignment of Numbers to Vertices
• Brunn-Minkowski Theory and Cauchy’s Surface Area Formula
• Convex Bodies The Brunn-MinkowskiTheory
• Edge-Isoperimetric Inequalities and Influences
• Edge-isoperimetric inequalities in the grid
• Edge-isoperimetric problem for Cayley graphs and generalized Takagi functions
• Isoperimetric inequalities and fractional set systems
• Optimal numberings and isoperimetric problems on graphs
• Sharp \(N^{3/4}\) law for the minimizers of the edge-isoperimetric problem on the triangular lattice
• The Brunn-Minkowski inequality
• The edge-isoperimetric problem for discrete tori
• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
• polymake: a framework for analyzing convex polytopes

Cited in

(2)

• General edge-isoperimetric inequalities. I: Information-theoretical methods
• Isoperimetry in integer lattices

Describes a project that uses

Uses Software

• polymake
• SageMath

This page was built for publication: A general method to determine limiting optimal shapes for edge-isoperimetric inequalities

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