{"id":"arxiv/2611.18633","url":"https://arxiv.org/abs/2611.18633","tags":["cs.SI","cs.AI","math.CO"],"score":0,"title":"Minimum cores in lattice graphs: zonotope structure and quartic growth","domain":"cs.SI","source":"arxiv","authors":["Navid Mehrdad"],"reviews":0,"subject":"cs.SI","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}