BOUNDED DILATION MAPS OF HYPERCUBES INTO CAYLEY-GRAPHS ON THE SYMMETRICAL GROUP

Let G and H be graphs with \V(G)\ less than or equal to \V(H)\. If f: V(G) --> V(H) is a one-to-one map, we let dilation(f) be the maximum o f dist(H)(f(x), f(y)) over all edges xy in G where dist(H) denotes dis tance in H. The construction of maps from G to H of small dilation is motivated by the problem of designing small slowdown simulations on H of algorithms that were originally designed for the network G. Let S(n ), the star network of dimension n, be the graph whose vertices are th e elements of the symmetric group of degree n, two vertices x and y be ing adjacent if x circle (1, i) = y for some i. That is, xy is an edge if x and y are related by a transposition involving some fixed symbol (which we take to be 1). Also let P(n), the pancake network of dimens ion n, be the graph whose vertices are the elements of the symmetric g roup of degree n, two vertices x and y being adjacent if one can be ob tained from the other by reversing some prefix. That is, xy is an edge if x and y are related by x circle (1, i)(2, i - 1)... ([i/2], [i/2]) = y. The star network (introduced in [AHK]) has nice symmetry propert ies, and its degree and diameter an sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube ne twork. These advantages of S(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hyper cube. The concern of this paper is to construct low dilation maps of h ypercube networks into star or pancake networks. Typically in such pro blems, there is a tradeoff between keeping the dilation small and simu lating a large hypercube. Our main result shows that al the cost of O( 1) dilation as n --> infinity, one can embed a hypercube of near optim um dimension into the star or pancake networks S(n) or P(n). More prec isely, letting Q(d) be the hypercube of dimension d, our main theorem is stated below. For simplicity, we state it only in the special case when the star network dimension is a power of 2. A more general result (applying to star networks of arbitrary dimension) is obtained by a s imple interpolation.