# zbMATH — the first resource for mathematics

On the extremal enumeration of $$\mathbb Z_n^2$$. (Russian) Zbl 1139.05065
Let $$D=\{0,1,\ldots ,n^2-1\}$$ and $$\sigma :\mathbb Z_n^2\rightarrow D$$ be a bijective function. Two elements $$a=(a_1,a_2),b=(b_1,b_2)\in \mathbb Z_n^2$$ are called neighbors and this relation is denoted by $$a\sim b$$ if $$a_i-b_i\in \{-1,0,1\}$$ for $$i=1,2$$. $$R(\sigma ,n)$$ denotes $$\max _{a\sim b}| \sigma (a)-\sigma (b)|$$ and $$R_n= \min _{\sigma} R(\sigma, n)$$. Consider the subset of cells of $$\mathbb Z^2$$ defined by $$K=\{k=\{(k_1,k_2), (k_1,k_2 +1),(k_1 +1,k_2),(k_1 +1,k_2 +1)\}:(k_1,k_2)\in \mathbb Z^2\}$$. The boundary of a set $$V$$ is defined by $$\partial V=\{a\in K\backslash V:\exists b\in V,a\sim b\}$$.
In this paper it is shown that $$\min _{V\subset K, | V| =n}| \partial V| \geq 2\sqrt{2n-1}+2$$. Some exact values are deduced, e. g., for all $$k=0,1,2\ldots$$, this minimum value equals $$4k+5$$ or $$4k+6$$ if $$2k^2+2k+1<| V| \leq 2k^2+3k+1$$ or $$2k^2+3k+1<| V| \leq 2k^2+4k+2$$, respectively. If in the definition of $$K$$ $$\mathbb Z^2$$ is replaced by $$\mathbb Z_n^2$$ then $$R_n\geq 2n-1$$. These results are applied to some trajectories on the torus $$(\mathbb R/\mathbb Z)^2$$.
##### MSC:
 05D05 Extremal set theory
##### Keywords:
isoperimetric problem; boundary; cell