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

zbMATH Open1355.05175arXiv1608.06373MaRDI QIDQ510340FDOQ510340

Authors: Ellen Veomett, E. Tsukerman 

Publication date: 17 February 2017

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

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.

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

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

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

zbMATH Keywords

latticesinfinite graphscontinuous isoperimetric problemdiscrete isoperimetric problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

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

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)