A local-global principle for vertex-isoperimetric problems
A total order \(\preceq\) on the vertex set of a graph \(G\) is called isoperimetric if the boundary (vertices at a distance \(1\)) of the sets of a fixed size is a minimum for the initial segment of that size in the order \(\preceq\), and if the ball (vertices at a distance at most \(1\)) is also an initial segment of the order \(\preceq\). Isoperimetric orders for the Cartesian powers \(G^n\) of a graph \(G\) under the simplicial order (vertices ordered by norm first and then lexicographically) \(\preceq^n\) for Cartesian products are studied. It is shown that the simplicial order \(\preceq^n\) is isoperimetric for each \(n \geq 1\) if and only if it is isoperimetric for \(n = 1, 2\).
scientific article; zbMATH DE number 1838994