Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.02199 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929234069422080 |
|---|---|
| author | Grytczuk, Jarosław Kisielewicz, Andrzej P. Przesławski, Krzysztof |
| author_facet | Grytczuk, Jarosław Kisielewicz, Andrzej P. Przesławski, Krzysztof |
| contents | Two axis-aligned boxes in $\mathbb{R}^d$ are \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$, but exact formulas are known only in three cases: $k=1$, $k=d-1$, and $k=d$. In particular, the formula $n(1,d)=d+1$ is equivalent to the famous theorem of Graham and Pollak on bipartite partitions of cliques.
In this paper we are dealing with the case $k=2$. We give a new construction of $k$-neighborly \emph{codes} giving better lower bounds on $n(2,d)$. The construction is recursive in nature and uses a kind of ``algebra'' on \emph{lists} of ternary strings, which encode neighborly boxes in a familiar way. Moreover, we conjecture that our construction is optimal and gives an explicit formula for $n(2,d)$. This supposition is supported by some numerical experiments and some partial results on related open problems which are recalled. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02199 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Neighborly boxes and bipartite coverings; constructions and conjectures Grytczuk, Jarosław Kisielewicz, Andrzej P. Przesławski, Krzysztof Combinatorics Two axis-aligned boxes in $\mathbb{R}^d$ are \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$, but exact formulas are known only in three cases: $k=1$, $k=d-1$, and $k=d$. In particular, the formula $n(1,d)=d+1$ is equivalent to the famous theorem of Graham and Pollak on bipartite partitions of cliques. In this paper we are dealing with the case $k=2$. We give a new construction of $k$-neighborly \emph{codes} giving better lower bounds on $n(2,d)$. The construction is recursive in nature and uses a kind of ``algebra'' on \emph{lists} of ternary strings, which encode neighborly boxes in a familiar way. Moreover, we conjecture that our construction is optimal and gives an explicit formula for $n(2,d)$. This supposition is supported by some numerical experiments and some partial results on related open problems which are recalled. |
| title | Neighborly boxes and bipartite coverings; constructions and conjectures |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.02199 |