Minimum cores in lattice graphs: zonotope structure and quartic growth
Source: arxiv.org/abs/2611.18633
A core of a graph is a nonempty vertex set in which every member has at least as many neighbours inside the set as outside. We study the minimum size $c_{m,n}$ of a finite core in the graph on $\Z^m$ joining points at sup-norm distance at most $n$. The local majority condition imposes a global geometric constraint: the convex hull of every core has an explicit lattice zonotope $H_n^{(m)}$ as a Minkowski summand. In the plane, this zonotope has width asymptotic to $6ζ(3)n^3/π^2$. We prove that all its lattice points form a core and construct a shell with $O(n^4)$ points. Together with a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.18633
curl -X POST /api/v1/records/arxiv/2611.18633/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18633/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'