The Edge-Isoperimetric Problem in (\mathbb{N}^2,\infty)

arXiv1205.6063MaRDI QIDQ6233315FDOQ6233315

Publication date: 28 May 2012

Abstract: We consider the edge-isoperimetric problem on the graph of the infinite grid

m a t h b b N^{2}

in the

e l l_{i n f t y}

metric. We first show that the solutions are not nested, so that techniques other than compressions have to be used. We then show that for any given volume of sets in

m a t h b b N^{2}

, there exists an optimal set of a specific geometric form and describe this form. We continue on to prove that the optimal perimeter has asymptotic growth rate

2 s q r t 7 x

as a function of the volume and obtain upper and lower bounds for the optimal perimeter which are within the small additive constant of

f r a c 352

of one another, thus effectively solving the discrete isoperimetric inequality on this graph. Finally, we prove that there exist arbitrarily long consecutive values of the volume for which the minimum perimeter is the same.

This page was built for publication: The Edge-Isoperimetric Problem in $(\mathbb{N}^2,\infty)$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6233315)