Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.20648 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908508051472384 |
|---|---|
| author | Grytczuk, Jarosław Kisielewicz, Andrzej P. Przesławski, Krzysztof |
| author_facet | Grytczuk, Jarosław Kisielewicz, Andrzej P. Przesławski, Krzysztof |
| contents | We study families of axis-aligned boxes in a $d$-dimensional Euclidean space $\mathbb{R}^d$ whose placement is restricted by bounds on the dimension of their pairwise intersections. More specifically, two such boxes in $\mathbb{R}^d$ are said to be \emph{$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 $\mathbb{R}^d$ is denoted by $n(k,d)$. It is known that $n(k,d)=Θ(d^k)$, for fixed $1\leqslant k\leqslant 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)\thicksim\frac{2^s+1}{2^{s+1}}\cdot2^d$, for every fixed $s\leqslant 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 \emph{joker}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20648 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Neighborly boxes and strings with jokers; constructions and asymptotics Grytczuk, Jarosław Kisielewicz, Andrzej P. Przesławski, Krzysztof Combinatorics We study families of axis-aligned boxes in a $d$-dimensional Euclidean space $\mathbb{R}^d$ whose placement is restricted by bounds on the dimension of their pairwise intersections. More specifically, two such boxes in $\mathbb{R}^d$ are said to be \emph{$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 $\mathbb{R}^d$ is denoted by $n(k,d)$. It is known that $n(k,d)=Θ(d^k)$, for fixed $1\leqslant k\leqslant 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)\thicksim\frac{2^s+1}{2^{s+1}}\cdot2^d$, for every fixed $s\leqslant 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 \emph{joker}. |
| title | Neighborly boxes and strings with jokers; constructions and asymptotics |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.20648 |