Dilation d Embedding of a Hyper-Pyramid into a Hypercube

摘要

The authors show that a P(k, d) hyper-pyramid can be embedded in a Boolean cube with minimal expansion and dilation d. The congestion is bounded from above by 2 to the (d + 1) power/d + 2 and from below by 1 + ((2 to the d power - d)/kd + 1). For P(k, 2) hyper-pyramids they present a dilation 2 and congestion 2 embedding. As a corollary a complete n-ary tree can be embedded in a Boolean cube with dilation max(2, (log sub 2)n) and expansion 2 to the (k((log sub 2)n)+1) power/(((n to the (k+1) power)-1)/(n - 1)). They also discuss multiple pyramid embeddings.