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 3: Stabilization and Compression
3.1 Introduction
In the literature on combinatorial isoperimetric problems on a graph G, there are two systematic ways in which Steiner operations have been constructed:
-
stabilization, based on certain kinds of reflective symmetry of G, and
-
compression, based on product decompositions of G with certain kinds of factors.
3.2 Stabilization
3.2.1 Diagrams
Recall that a diagram is a graph whose vertices are points in 
, d-dimensional Euclidean space, and whose edges are arcs connecting pairs of vertices. The edges need not be straight lines, though they may always be taken as such, and may even intersect at interior points. In Chapter 1 planar diagrams were just used to give a visual representation of graphs but now we wish to take advantage of the geometry of the ambient space, so let us define these representations more carefully.
3.2.1.1 The n-gon, 
n
The vertices of n are the nth roots of unity (in 
2),
and its edges are circular arcs
with ? ( e k) = { ? k , ? k +1(mod n )} .
3.2.1.2 The d-cube, 
d
The vertices are 
= { ?1, 1} d ? . The edges,
are represented by the straight-line segments determined by each such pair, i.e. for e ? with ? ( e) = { x, y} , e is represented by the arc
3.2.1.3 The d-crosspolytope, 
d
Let ? ( k )
Copyright Cambridge University Press 2004 under license agreement with Books24x7
