The cubicity of hypercube graphs

For a graph G, its cubicity cub(G) is the minimum dimension k such that G is representable as the intersection graph of (axis-parallel) cubes in k-dimensional space. (A k-dimensional cube is a Cartesian product R-1 x R-2 x ... x R-k, where R-i is a closed interval of the form [a(i), a(i) + 1] on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113-118] showed that for a d-dimensional hypercube H-d, d-1/log d <= cub(H-d) <= 2d. In this paper, we use the probabilistic method to show that cub(H-d)=Theta(d/log d). The parameter boxicity generalizes cubicity: the boxicity box(G) of a graph G is defined as the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes in k-dimensional space. Since box(G) :5 cub(G) for any graph G, our result implies that box(H-d) = O (d/log d). The problem of determining a non-trivial lower bound for box(H-d) is left open. (C) 2007 Elsevier B.V. All rights reserved.