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

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

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.

Review text

Summary: We consider the family of graphs whose vertex set is \(\mathbb{Z}^k\) where two vertices are connected by an edge when their \(\ell_\infty\)-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 \mathbb{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

(16)

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

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)