A subset of vertices of a graph is minimal if, within all subsets of the same size, its vertex boundary is minimal. We give a complete, geometric characterization of minimal sets for the planar integer lattice $X$. Our characterization elucidates the structure of all minimal sets, and we are able to use it to obtain several applications. We show that the neighborhood of a minimal set is minimal. We characterize uniquely minimal sets of $X$: those which are congruent to any other minimal set of the same size. We also classify all efficient sets of $X$: those that have maximal size amongst all such sets with a fixed vertex boundary. We define and investigate the graph $G$ of minimal sets whose vertices are congruence classes of minimal sets of $X$ and whose edges connect vertices which can be represented by minimal sets that differ by exactly one vertex. We prove that G has exactly one infinite component, has infinitely many isolated vertices and has bounded components of arbitrarily large size. Finally, we show that all minimal sets, except one, are connected.
@article{10_37236_10055,
author = {Radhika Gupta and Ivan Levcovitz and Alexander Margolis and Emily Stark},
title = {Planar lattice subsets with minimal vertex boundary},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/10055},
zbl = {1473.05307},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10055/}
}
TY - JOUR
AU - Radhika Gupta
AU - Ivan Levcovitz
AU - Alexander Margolis
AU - Emily Stark
TI - Planar lattice subsets with minimal vertex boundary
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/10055/
DO - 10.37236/10055
ID - 10_37236_10055
ER -
%0 Journal Article
%A Radhika Gupta
%A Ivan Levcovitz
%A Alexander Margolis
%A Emily Stark
%T Planar lattice subsets with minimal vertex boundary
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10055/
%R 10.37236/10055
%F 10_37236_10055
Radhika Gupta; Ivan Levcovitz; Alexander Margolis; Emily Stark. Planar lattice subsets with minimal vertex boundary. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/10055
