Towards a Complete Local-Global Principle

Abstract Ahlswede and Cai proved that if a simple graph has nested solutions under the edge-isoperimetric problems, and the lexicographic order produces nested solutions for its second cartesian power, then the lexicographic order produces nested solutions for any finite cartesian power. Under very general assumptions, we prove that if a graph and its second cartesian power have nested solutions, then so does any finite cartesian power. This is achieved by proving that the lexicographic order and colexcographic order are the only possible nested solutions in many cases. Harper asked if this is true without any restriction. We also conjecture that it is. All graphs studied in the literature for which the lexicographic order is optimal are regular. This lead Bezrukov and Elsässer to conjecture that if the lexicographic order is optimal for the second cartesian power, then the original graph is regular. A counterexample to this conjecture is provided.