New bounds on the maximum number of neighborly boxes in R^d

A family of axis-aligned boxes in R^d is k-neighborly if the intersection of every two of them has dimension at least d−k and at most d−1. Let n(k,d) denote the maximum size of such a family. It is known that n(k,d) can be equivalently defined as the maximum number of vertices in a complete graph whose edges can be covered by d complete bipartite graphs, with each edge covered at most k times. We derive a new upper bound on n(k,d), which implies, in particular, that n(k,d)⩽(2−δ)^d if k⩽(1−ɛ)d, where δ>0 depends on arbitrarily chosen ɛ>0. The proof applies a classical result of Kleitman, concerning the maximum size of sets with a given diameter in discrete hypercubes. By an explicit construction we obtain also a new lower bound for n(k,d), which implies that [Formula presented]. We also study k-neighborly families of boxes with additional structural properties. Families called total laminations, that split in a tree-like fashion, turn out to be particularly useful for explicit constructions. We pose a few conjectures based on these constructions and some computational experiments.