The cubicity of hypercube graphs

For a graph GG, its cubicity  cub(G) is the minimum dimension kk such that GG is representable as the intersection graph of (axis-parallel) cubes in kk-dimensional space. (A kk-dimensional cube is a Cartesian product R1×R2×⋯×RkR1×R2×⋯×Rk, where RiRi is a closed interval of the form [ai,ai+1][ai,ai+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 dd-dimensional hypercube HdHd, d−1logd≤cub(Hd)≤2d. In this paper, we use the probabilistic method to show that cub(Hd)=Θ(dlogd). The parameter boxicity   generalizes cubicity: the boxicity box(G) of a graph GG is defined as the minimum dimension kk such that GG is representable as the intersection graph of axis-parallel boxes in kk-dimensional space. Since box(G)≤cub(G) for any graph GG, our result implies that box(Hd)=O(dlogd). The problem of determining a non-trivial lower bound for box(Hd) is left open.