Vertex isoperimetric inequalities for a family of graphs on Z^k

MaRDI QIDQ456299zbMATH OpenFDO

Authors Ellen Veomett, Andrew John Radcliffe

Publication date 24 October 2012

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

Full work available at URL https://arxiv.org/abs/1202.4204, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p45

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

discrete isoperimetric inequalities

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Abstract: We consider the family of graphs whose vertex set is Z^k where two vertices are connected by an edge when their linfty-distance is 1. We prove the optimal vertex isoperimetric inequality for this family of graphs. That is, given a positive integer n, we find a set A subset Z^k of size n such that the number of vertices who share an edge with some vertex in A is minimized. These sets of minimal boundary are nested, and the proof uses the technique of compression. We also show a method of calculating the vertex boundary for certain subsets in this family of graphs. This calculation and the isoperimetric inequality allow us to indirectly find the sets which minimize the function calculating the boundary.

Recommendations

• An approximate vertex-isoperimetric inequality for r-sets
• Compressions and isoperimetric inequalities
• Isoperimetry in integer lattices
• The vertex isoperimetric problem for the powers of the diamond graph
• Publication:4888931

Cited in

(14)

• Planar lattice subsets with minimal vertex boundary
• An extremal graph problem on a grid and an isoperimetric problem for polyominoes
• Vertex isoperimetric parameter of a computation graph
• On a characterization of lattice cubes via discrete isoperimetric inequalities
• An approximate vertex-isoperimetric inequality for r-sets
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Interpolating between volume and lattice point enumerator with successive minima
• Isoperimetry in integer lattices
• A general method to determine limiting optimal shapes for edge-isoperimetric inequalities
• The vertex-isoperimetric number of the incidence and non-incidence graphs of unitals
• Isoperimetric stability in lattices
• The vertex isoperimetric problem for the powers of the diamond graph
• On discrete Brunn-Minkowski and isoperimetric type inequalities

This page was built for publication: Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)

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