n(2,d) asymptotic limit ½

Conjecture on the asymptotic of n(2,d) · arXiv:2212.05133

arXiv Informal medium confidence— first stated 2023-03-03

Authors: Noga Alon, Jarosław Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przesławski

Status partial medium confidence

The conjecture that $\lim_{d\to\infty} n(2,d)/d^2 = 1/2$ remains open. A 2024 follow-up by Grytczuk, Kisielewicz, and Przesławski (arXiv:2402.02199) gives new recursive constructions of 2-neighborly families improving the lower bound on $n(2,d)$, and poses an explicit conjectured formula for $n(2,d)$ based on their construction being optimal — this is partial progress but does not resolve the asymptotic limit. A 2025 paper (arXiv:2508.20648) on 'strings with jokers' addresses the regime $k$ close to $d$ (proving $n(d-s,d) \sim \frac{2^s+1}{2^{s+1}} \cdot 2^d$) but does not directly resolve the $k=2$ question.

Cited literature (2)

partial Neighborly boxes and bipartite coverings; constructions and conjectures (2024)

Jarosław Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przesławski · arXiv preprint · arXiv:2402.02199

Provides improved lower bounds on n(2,d) via a new recursive construction using 'algebra on ternary strings', conjectures that this construction is optimal and yields an explicit formula for n(2,d), but does not prove the asymptotic limit 1/2.
partial Neighborly boxes and strings with jokers; constructions and asymptotics (2025)

authors not fully retrieved · arXiv preprint · arXiv:2508.20648

Proves n(d-s,d) ~ (2^s+1)/(2^(s+1)) * 2^d for fixed s, improving lower bounds when k is close to d; does not directly address the k=2 asymptotic conjecture.

Reviewer notes. The conjecture from arXiv:2212.05133 that lim n(2,d)/d^2 = 1/2 is still open as of 2026. The follow-up arXiv:2402.02199 improves the lower bound and poses a more explicit conjecture about n(2,d), but does not settle the asymptotic constant. The 2025 paper arXiv:2508.20648 targets a different parameter regime (k near d). Full text of 2402.02199 was not retrievable (HTML 404), so the precise relationship between its conjecture and the 1/2 limit could not be verified; confidence is medium.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. A general conjecture is posed in the final section which, together with the lower bound $n(2,d) > (1-o(1))\frac{d^2}{2}$, would imply that $\lim_{d\to\infty} \frac{n(2,d)}{d^2} = \frac{1}{2}$.

Context

The authors establish the lower bound $n(2,d) > (1-o(1))\frac{d^2}{2}$, improving the previous bound $n(2,d) > \frac{d^2}{4}$. They remark that determining the precise asymptotic order of $n(2,d)$ seems to be a hard task (as noted earlier by Alon and by Huang–Sudakov), and refer to a formal conjecture in the final section concerning lamination-based constructions.

Notes. The formal conjecture appears in Section 3 (the final section on total laminations and computational experiments), which is not present in the provided PDF extract. Only the informal forward-reference in the introduction is available; math may be garbled due to PDF source.

Source paper

New bounds on the maximum number of neighborly boxes in R^d
Noga Alon, Jarosław Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przesławski · 2023-03-03
https://arxiv.org/abs/2212.05133 PDF source