We study families of axis-aligned boxes in a d-dimensional Euclidean space Rᵈ whose placement is restricted by bounds on the dimension of their pairwise intersections. More specifically, two such boxes in Rᵈ are said to be k-neighborly if their intersection has dimension at least d-k and at most d-1. The maximum number of pairwise k-neighborly boxes in Rᵈ is denoted by n (k, d). It is known that n (k, d) =Θ (dᵏ), for fixed 1 k d, however, exact formulas are known only in three cases: k=1, k=d-1, and k=d. In particular, the equality n (1, d) =d+1 is equivalent to the famous theorem of Graham and Pollak concerning partitions of complete graphs into complete bipartite graphs. In our main result we give a new construction of families of k-neighborly boxes which improves the lower bound for n (k, d) when k is close to d. Together with some recent upper bounds on n (k, d), it gives the asymptotic equality n (d-s, d) 2ˢ+12^{s+1}2ᵈ, for every fixed s d/2. In our constructions we use a familiar interpretation of the problem in the language of Hamming cubes represented by binary strings with a special blank symbol, called joker.
Grytczuk et al. (Thu,) studied this question.