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\).
05D05 Extremal set theory