The cubicity of hypercube graphs

AbstractFor 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 R1×R2×⋯×Rk, where Ri is a closed interval of the form [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 d-dimensional hypercube Hd, 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 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)≤cub(G) for any graph G, our result implies that box(Hd)=O(dlogd). The problem of determining a non-trivial lower bound for box(Hd) is left open