Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs
Abstract
We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer r≥0, the radius-r neighbourhoods of a unit-cube graph in ℝ3 have bounded VC-dimension. Our bound is 22O(r), independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of three-dimensional generalized dominance relations. Its proof uses groups ordered in two coordinates, with neighbouring groups acting as barriers that preserve this invariant when one layer is removed. Combining these bounds with the existing interval-representation framework, we obtain a Las Vegas algorithm that, for every fixed integer Δ≥1, decides whether a graph given by n cube centres has diameter at most Δ in expected OΔ(n2−εΔ) time, for an explicit constant εΔ>0. Finally, for every integer r≥7, we construct unit-cube graphs with rational centres whose radius-r neighbourhoods have VC-dimension Ω(r3).
Related
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- Minimizing the spectral radius of unicyclic graphs with fixed order and dissociation number
- A hybrid TT/QTT discontinuous Galerkin method with fixed-matrix upwinding for three-dimensional transient multigroup neutron transport
- Compact Toeplitz Operators and the Geometry of Fixed-Radius Averages
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
BibTeX
@misc{zhang2026fixedradius,
title = {{Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs}},
author = {Guangjian Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06747},
eprint = {2611.06747},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06747},
}
RIS
TY - UNPB
TI - Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs
AU - Guangjian Zhang
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06747
UR - https://arxiv.org/abs/2611.06747
AB - We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer r≥0, the radius-r neighbourhoods of a unit-cube graph in ℝ^3 have bounded VC-dimension. Our bound is 2^2^O(r), independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of three-dimensional generalized dominance relations. Its proof uses groups ordered in two coordinates, with neighbouring groups acting as barriers that preserve this invariant when one layer is removed. Combining these bounds with the existing interval-representation framework, we obtain a Las Vegas algorithm that, for every fixed integer Δ≥1, decides whether a graph given by n cube centres has diameter at most Δ in expected O_Δ(n^2−ε_Δ) time, for an explicit constant ε_Δ>0. Finally, for every integer r≥7, we construct unit-cube graphs with rational centres whose radius-r neighbourhoods have VC-dimension Ω(r^3).
ER -