## Abstract

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.

Original language | English (US) |
---|---|

Article number | 103797 |

Journal | European Journal of Combinatorics |

Volume | 114 |

DOIs | |

State | Published - Dec 2023 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'New bounds on the maximum number of neighborly boxes in R^{d}'. Together they form a unique fingerprint.