{"id":"arxiv/2611.06747","url":"https://arxiv.org/abs/2611.06747","tags":["cs.CG","math.CO"],"score":0,"title":"Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs","domain":"cs.CG","source":"arxiv","authors":["Guangjian Zhang"],"reviews":0,"subject":"cs.CG","summary":"We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer $r\\ge0$, the radius-$r$ neighbourhoods of a unit-cube graph in $\\mathbb{R}^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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}