Tight asymptotic dimension bound for intersection graphs

Optimal bound question · arXiv:2202.07293

arXiv Informal medium confidence— first stated 2022-10-04

Authors: Zdeněk Dvořák, Sergey Norin

Status open high confidence

The question of whether the asymptotic dimension bound of $2n+1$ in Theorems 1–2 of the source paper can be decreased to $n$ remains open. The lower bound of $n$ is already established in the source paper via $n$-dimensional grids as touching graphs of balls in $\mathbb{R}^n$. A 2025 follow-up (arXiv:2504.00932, SoCG 2025) proves that all sphere intersection graphs in $\mathbb{R}^d$ have asymptotic dimension at most $2d+2$, and that $K_{t,t}$-free subclasses admit strongly sublinear separators; this does not close the gap between $n$ and $2n+1$.

Cited literature (1)

partial Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs (2025)

Davies, Georgakopoulos, Hatzel, McCarty · 41st International Symposium on Computational Geometry (SoCG 2025), LIPIcs · arXiv:2504.00932 · doi:10.4230/LIPIcs.SoCG.2025.36

Proves that sphere intersection graphs in $\mathbb{R}^d$ have asymptotic dimension at most $2d+2$ and that $K_{t,t}$-free subclasses admit strongly sublinear separators; does not improve the bound toward $n$.

Reviewer notes. The conjecture asks whether the upper bound $2n+1$ can be reduced to $n$; the source paper already gives $n$ as a lower bound. The only relevant post-2022 work found is arXiv:2504.00932 (SoCG 2025), which obtains $2d+2$ for sphere intersection graphs (without bounded aspect-ratio hypothesis) but does not make progress toward $n$. No paper resolving the optimal bound question was found.

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

Informal. Is it possible to decrease the bound to $n$ in Theorem 2 (or at least in Theorem 1)?

Context

The paper proves that intersection graphs of $f$-space-filling systems of subsets of a metric space of Assouad-Nagata dimension $n$ have asymptotic dimension at most $2n+1$. The authors remark that this bound is likely not optimal, noting that interval graphs (intersection graphs of balls in $\mathbb{R}^1$) have asymptotic dimension $1$ rather than $3$. They also observe that $n$-dimensional grids have asymptotic dimension $n$ and can be represented as touching graphs of balls in $\mathbb{R}^n$, so the bound cannot be decreased below $n$.

Notes. PDF source — stated as 'it is natural to ask' without a labelled theorem environment.

Source paper

Asymptotic dimension of intersection graphs
Zdeněk Dvořák, Sergey Norin · 2022-10-04
https://arxiv.org/abs/2202.07293 PDF source