no. 16 · Tuesday 17 November 2026
Minimum cores in lattice graphs: zonotope structure and quartic growth
Abstract
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 packing argument, this gives $c_{2,n}=Θ(n^4)$ and coordinate widths $Θ(n^3)$ for every minimum core. We determine $c_{2,1}=12$ and $c_{2,2}=96$ by analytic arguments and prove uniqueness up to translation in both cases. Explicit forced-set and deficit certificates determine further minima within the prescribed zonotope hull. We distinguish these restricted results from global optimality and state the remaining geometric conjectures. We also give a direct reduction from \textsc{Clique} showing that the core problem is NP-complete on general finite graphs, which settles a conjecture of Hassanpour in the terms in which it was posed.
- fields
- Combinatorics