On the size of identifying codes in binary hypercubes (Q1024996): Difference between revisions

A binary Hamming space of dimension \(n\) is denoted by \(\mathbb{F}^n\). For a code \(C \subseteq \mathbb{F}^n\) and a set \(X \subseteq \mathbb{F}^n\), the codeword \(r\)-neighborhood of \(X\) is \(I_r(C;X) := B_r(X) \cap C\), where \(B_r(X)\) is the union of the balls of radius \(r\) centered at the elements of \(X\). A code is said to be \((r,\leq \ell)\)-identifying if for all \(X,Y \subseteq \mathbb{F}^n\) such that \(|X| \leq \ell\), \(|Y| \leq \ell\), and \(X \neq Y\) we have \(I_r(C;X) \neq I_r(C;Y)\). \textit{I. Honkala} and \textit{A. Lobstein} [J. Comb. Theory, Ser. A 99, No. 2, 232--243 (2002; Zbl 1005.94030)] determined the asymptotic behaviour of the smallest possible cardinality of \((r,\leq \ell)\)-identifying codes, for \(\ell = 1\) and \(r = \lfloor {\rho}n \rfloor\), \(\rho < 1\). The current work extends this result to any fixed \(\ell\) and \(\rho < 1/2\). Other results obtained include a construction of small \((r,\leq 2)\)-identifying codes for \(r = \lfloor n/2 \rfloor - 1\).