Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
6.5: Comments
6.5 Comments
Bezrukov and Els sser [20] showed that powers of the graphs K 2 n ? ( I 1 + I 2 + + I m), where { I j} is a parallel family of disjoint complete matchings in K 2 n and m ? n/2, have lex nested solutions for EIP. The graph of 
d is isomorphic to K 2 d ? I 1, so this result is related to our Theorem 6.6. Their proof is another application of the Ahlswede Cai theorem (Theorem 6.3), but the result has broader significance because it gives an isoperimetric inequality on all regular graphs with the same number of vertices and edges. They state similar results for powers of bipartite graphs K n, n ? ( I 1 + I 2 + + I m), m ? n/2.
T. Carlson [25] used the logic of Bezrukov, Els sser and Das to show that powers of 
5 have nested solutions. The optimal numbering is again not lexicographic. Since 5 is a face of the dodecahedron ( V 20) and the Petersen graph is the quotient of V 20 by its antipodal symmetry, the obvious next question to consider in this direction is whether the powers of V 20 have nested solutions for the EIP? A recent computer calculation by Bezrukov has shown that it does not.
Exercise 6.12
Does the pairwise...
Copyright Cambridge University Press 2004 under license agreement with Books24x7
