Optimal Subcube Embeddability in Hypercubes with Additional Dimension

摘要

Subcube embeddability of the hypercube can be enhanced by introducing an additional dimension. A set of new dimensions, characterized by the Hamming distance between the pairs of nodes it connects, is introduced using a measure defined as the magnitude of a dimension. An enumeration of subcubes of various size is presented for a dimension parameterized by its magnitude. It is shown that the maximum number of subcubes for a Q_n can only be attained when the magnitude of dimension is n - 1 or n.