Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs
Source: arxiv.org/abs/2611.06747
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.06747
curl -X POST /api/v1/records/arxiv/2611.06747/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06747/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'