×

A general method to determine limiting optimal shapes for edge-isoperimetric inequalities. (English) Zbl 1355.05175

Summary: 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.

MSC:

05C63 Infinite graphs
05C12 Distance in graphs

Software:

polymake; SageMath
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Alexander Barvinok. A course in convexity, volume 54 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2002. · Zbl 1014.52001
[2] B´ela Bollob´as and Imre Leader. An isoperimetric inequality on the discrete torus. SIAM J. Discrete Math., 3(1):32-37, 1990. · Zbl 0746.05031
[3] B´ela Bollob´as and Imre Leader. Edge-isoperimetric inequalities in the grid. Combinatorica, 11(4):299-314, 1991. · Zbl 0755.05045
[4] B´ela Bollob´as and Imre Leader. Isoperimetric inequalities and fractional set systems. J. Combin. Theory Ser. A, 56(1):63-74, 1991. · Zbl 0731.05044
[5] Thomas A. Carlson. The edge-isoperimetric problem for discrete tori. Discrete Math., 254(1-3):33-49, 2002. · Zbl 1004.05038
[6] H. S. M. Coxeter. Regular Polytopes. Methuen & Co., Ltd., London; Pitman Publishing Corporation, New York, 1948; 1949. · Zbl 0031.06502
[7] Elisa Davoli, Paolo Piovano, and Ulisse Stefanelli. Sharp n3/4law for the minimizers of the edge-isoperimetric problem on the triangular lattice, to appear J. Nonlinear Sci. the electronic journal of combinatorics 24(1) (2017), #P1.2621 · Zbl 1383.82063
[8] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 5.10), 2011.http://www.sagemath.org.
[9] Dvir Falik and Alex Samorodnitsky. Edge-isoperimetric inequalities and influences. Combin. Probab. Comput., 16(5):693-712, 2007. · Zbl 1134.05309
[10] R. J. Gardner. The Brunn-Minkowski inequality. Bull. Amer. Math. Soc. (N.S.), 39(3):355-405, 2002. · Zbl 1019.26008
[11] Ewgenij Gawrilow and Michael Joswig. polymake: a framework for analyzing convex polytopes. In Gil Kalai and G¨unter M. Ziegler, editors, Polytopes — Combinatorics and Computation, pages 43-74. Birkh¨auser, 2000. · Zbl 0960.68182
[12] L. H. Harper. Optimal numberings and isoperimetric problems on graphs. J. Combinatorial Theory, 1:385-393, 1966. · Zbl 0158.20802
[13] L. H. Harper. Global methods for combinatorial isoperimetric problems, volume 90 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2004. · Zbl 1043.05002
[14] Vsevolod F. Lev. Edge-isoperimetric problem for Cayley graphs and generalized Takagi functions. SIAM J. Discrete Math., 29(4):2389-2411, 2015. · Zbl 1328.05089
[15] John H. Lindsey, II. Assignment of numbers to vertices. Amer. Math. Monthly, 71:508-516, 1964. · Zbl 0279.05019
[16] Oliver Riordan. An ordering on the even discrete torus. SIAM J. Discrete Math., 11(1):110-127 (electronic), 1998. · Zbl 0914.05038
[17] Alex Samorodnitsky. An inequality for functions on the hamming cube. Combinatorics, Probability, and Computing. To appear. · Zbl 1371.05275
[18] Rolf Schneider. Convex bodies: the Brunn-Minkowski theory, volume 151 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, expanded edition, 2014. · Zbl 1287.52001
[19] Emmanuel Tsukerman and Ellen Veomett. A simple proof of cauchy’s surface area formula.arXiv:1604.05815. · Zbl 1391.52008
[20] Ellen Veomett and A. J. Radcliffe. Vertex isoperimetric inequalities for a family of graphs on Zk. Electron. J. Combin., 19(2):#P45, 2012. · Zbl 1252.05094
[21] Wikipedia.Truncated 24-cells.https://en.wikipedia.org/wiki/Truncated_24-cells#cite_ref-Gevay_1-0, 2016.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.