Minimal partitions of a box into boxes

A box is a set of the form X = X-1 x...x X-d, for some finite sets X-i, i = 1,...,d. Answering a question posed by Kearnes and Kiss [ 2], Alon, Bohman, Holzman and Kleitman proved [ 1] that any partition of X into nonempty sets of the form A(1) x...x A(d), with A(i) not subset of or equal to X-i, must contain at least 2 d members. In this paper we explore properties of such partitions with minimum possible number of parts. In particular, we derive two characterizations of minimal partitions among all partitions of X into proper boxes. For instance, let P = P-1 x...x P-d be a fixed k-dimensional plane in X, that is P-i = X-i for exactly k different subscripts i, with \P-i\ = 1 otherwise. It is shown that F is a minimal partition of X if and only if P intersects exactly 2(k) members of F, for every such P.