A local–global principle for vertex-isoperimetric problems Original Research Article

We consider the vertex-isoperimetric problem (VIP) for cartesian powers of a graph G. A total order ≼ on the vertex set of G is called isoperimetric if the boundary of sets of a given size k is minimum for any initial segment of ≼, and the ball around any initial segment is again an initial segment of ≼. We prove a local–global principle with respect to the so-called simplicial order on Gn (see Section 2 for the definition). Namely, we show that the simplicial order ≼n is isoperimetric for each n⩾1 iff it is so for n=1,2. Some structural properties of graphs that admit simplicial isoperimetric orderings are presented. We also discuss new relations between the VIP and Macaulay posets.