Nerve-type and invariance theorems for asymptotic dimension
2026-07-27 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study how the large-scale complexity of a graph made from overlapping sets relates to the space those sets live in. They show that if the space has a certain dimension measure (Assouad-Nagata dimension) equal to n, and the sets satisfy some intersection limits, then the graph's dimension (asymptotic dimension) is at most n+1. They apply this to shapes like balls in n-dimensional space, confirming the graph's dimension is at most n+1. They also find that for connected sets with connected boundaries, the graph's dimension depends only on the boundaries' intersection graph. For example, graphs from spheres in n-dimensional space have dimension n or n+1 when n is at least 2.
Asymptotic dimensionAssouad-Nagata dimensionMetric spaceIntersection graphCovering dimensionTopological spaceCompact convex setsBounded aspect ratioConnected boundarySpheres in R^n
Authors
Chun-Hung Liu, Sergey Norin
Abstract
Asymptotic dimension of metric spaces is a large-scale analog of covering dimension of topological spaces. An intersection graph of a family of sets is the graph whose vertices are the members of the family and whose edges correspond to pairs of members with non-empty intersection. Our first main result connects the asymptotic dimension of the intersection graph of a family ${\mathcal F}$ and the Assouad-Nagata dimension of the ambient metric space containing members of ${\mathcal F}$ under some mild and necessary assumptions. We prove that if ${\mathcal F}$ is a family of subsets of a metric space of Assouad-Nagata dimension $n$ such that every ball of radius $r$ intersects at most $f(r/s)$ pairwise disjoint members of ${\mathcal F}$ of diameter at least $s$ for some function $f$, then the asymptotic dimension of the intersection graph of ${\mathcal F}$ is at most $n+1$. This result is optimal both quantitatively and qualitatively in several senses. As a corollary of this result, the asymptotic dimension of the intersection graph of any family of compact convex sets of bounded aspect ratio in ${\mathbb R}^n$, such as a family of balls in ${\mathbb R}^n$, is at most $n+1$. Our second main result states that the asymptotic dimension of the intersection graph of a family ${\mathcal F}$ of connected closed sets of a connected topological space with connected boundary equals the asymptotic dimension of the intersection graph of the family of the boundary of the sets in ${\mathcal F}$, under a mild condition. In particular, the asymptotic dimension of the intersection graphs of families of spheres in ${\mathbb R}^n$ equals $n$ or $n+1$ when $n \geq 2$.