NEAR EMBEDDINGS OF HYPERCUBES INTO CAYLEY-GRAPHS ON THE SYMMETRICAL GROUP

Simulations of hypercube networks by certain Cayley graphs on the symmetric group are investigated. Let Q(k) be the familiar k-dimensional hypercube, and let S(n) be the star network of dimension n defined as follows. The vertices of S(n) are the elements of the symmetric group of degree n, two vertices x and y being adjacent if x . (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). This network has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages of S(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The first step in such a simulation is the construction of a one-to-one map f : Q(k) --> S(n) of dilation d, for d small. That is, one wants a map f such that images of adjacent points are at most distance d apart in S(n). An alternative approach, best applicable when one-to-one maps are difficult or impossible to find, is the construction of a one-to-many map g of dilation d, defined as follows. For each point x is-an-element-to Q(k), there is an associated subset g(x) subset-or-equal-to V(S(n)) such that for each edge xy in Q(k), every x' is-an-element-of g(x) is at most distance d in S(n) from some y' is-an-element-of g(y). Such one-to-many maps allow one to achieve the low interprocessor communication time desired in the usual one-to-one embedding underlying a simulation. This is done by capturing the local structure of Q(k) inside of S(n) (via the one-to-many embedding) when the global structure cannot be so captured. Our results are the following. 1) There exit the following one-to-many embeddings: a) f : Q(k) --> S(3k + 1) with dilation (f) = 1; b) f : Q(11k + 2) --> S(13k + 2) with dilation (f) = 2. 2) There exists a one-to-one embedding f : Q(n2n-1) --> S(2n) with dilation (f) = 3.