2022/12/09 by Alon, Noga, Grytczuk, Jarosław, Kisielewicz, Andrzej P. +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2212.05133
A family of axis-aligned boxes in \erd 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)\leqslant (2-δ)d if k\leqslant (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 n(k,d)\geqslant (1-o(1))(dk)/(k!). 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.