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.
Radhika Gupta
1
;
Ivan Levcovitz
2
;
Alexander Margolis
3
;
Emily Stark
4
1
Temple University
2
Technion - Israel Institute of Technology
3
Vanderbilt University
4
Wesleyan University
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
@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
