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
Chapter 5: Stronger Stabilization
In this chapter we strengthen the theory of stabilization by:
-
utilizing Coxeter s theory of groups generated by reflections to
-
facilitate the calculation of stability orders, and
-
generate a large family of graphs to which stabilization applies:
-
-
weakening the requirement for a reflective symmetry of a graph to be stabilizing so that stabilization applies to a larger class of diagrams.
5.1 Graphs of Regular Solids
The edge-isoperimetric problem (EIP) and VIP are NP-complete in general but, as we have seen, a number of special cases, important in applications, have been solved and many of the solved cases are highly symmetric. In the early 1970s I became intrigued with the EIP on the graph of the dodecahedron. The idea was to take the combinatorial isoperimetric problems whose development had been motivated by applications to engineering, and rethink them from the viewpoint of pure mathematics. It is not difficult, assuming that the EIP on the dodecahedron has nested solutions, to find an optimal numbering, and that numbering has structure similar to lex on Q d. The challenge was to prove that its initial segments are solution sets. Since the dodecahedron, unlike the d-cube, does not factor as a product of subgraphs, compression will not work. Something new is required. In the late 1970s, having successfully developed a notion of morphism for optimal flow problems (the subject of a projected second volume on global methods), I decided to take up the challenge. One of the things which had...
Copyright Cambridge University Press 2004 under license agreement with Books24x7
