Back to Search
Start Over
Exact values and improved bounds on $k$-neighborly families of boxes
- Source :
- European J. Combin. 118 (2024), Paper No. 103926, 17pp
- Publication Year :
- 2023
-
Abstract
- A finite family $\mathcal{F}$ of $d$-dimensional convex polytopes is called $k$-neighborly if $d-k\le\textup{dim}(C\cap C')\le d-1$ for any two distinct members $C,C'\in\mathcal{F}$. In 1997, Alon initiated the study of the general function $n(k,d)$, which is defined to be the maximum size of $k$-neighborly families of standard boxes in $\mathbb{R}^{d}$. Based on a weighted count of vectors in $\{0,1\}^{d}$, we improve a recent upper bound on $n(k,d)$ by Alon, Grytczuk, Kisielewicz, and Przes\l awski for any positive integers $d$ and $k$ with $d\ge k+2$. In particular, when $d$ is sufficiently large and $k\ge 0.123d$, our upper bound on $n(k,d)$ improves the bound $\sum_{i=1}^{k}2^{i-1}\binom{d}{i}+1$ shown by Huang and Sudakov exponentially. Furthermore, we determine that $n(2,4)=9$, $n(3,5)=18$, $n(3,6)=27$, $n(4,6)=37$, $n(5,7)=74$, and $n(6,8)=150$. The stability result of Kleitman's isodiametric inequality plays an important role in the proofs.<br />Comment: Final version, accepted by European Journal of Combinatorics
- Subjects :
- Mathematics - Combinatorics
05C70
Subjects
Details
- Database :
- arXiv
- Journal :
- European J. Combin. 118 (2024), Paper No. 103926, 17pp
- Publication Type :
- Report
- Accession number :
- edsarx.2301.06485
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.ejc.2024.103926