Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\) (Q456299)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\) |
scientific article |
Statements
Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\) (English)
0 references
24 October 2012
0 references
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.
0 references
discrete isoperimetric inequalities
0 references