Neighborly boxes and strings with jokers; constructions and asymptotics

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ˢ⁺¹·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.