Codes for identification in the king lattice (Q1423495)

Let \(G=(V,E)\) be an undirected graph and \(C\subseteq V\). Let \(B_{r}(F)\) denote the set of all vertices that are within distance \(r\) from at least one vertex in \(F\). If the sets \(B_{r}(F)\cap C\) are distinct for all subsets \(F\) of \(V\) with at most \(k\) elements, then \(C\) is called an \((r,\leq k)\)-identifying code in \(G\). In this paper the graph \(G\) is the two-dimensional square lattice with diagonals. Its vertex set is \(V=\mathbb{Z}^{2}\), and two vertices are connected by an edge if their Euclidean distance is at most \(\sqrt{2}\). The density of \(C\) is defined as \(D(C)=\limsup _{n\rightarrow \infty}| C\cap Q_{n}| /| Q_{n}| \), where \(Q_{n}\) denotes the set of vertices \((x,y)\in V\) with \(| x| \leq n\) and \(| y| \leq n\). It is shown that the optimal density of an \((r,\leq 2)\)-identifying code is \(1/4\) for all \(r\geq 3\). For \(r=1,2\), constructions with densities \(3/7\) and \(3/10\) are given, and the corresponding lower bounds \(9/22\) and \(31/120\) are proved. Notice that the problem of determining the optimal density of an \((r,\leq k)\)-identifying code has been settled for all values of \(r\geq 1\) when \(k=1\).