On the size of identifying codes in binary hypercubes
| dc.creator | Janson, Svante | |
| dc.creator | Laihonen, Tero | |
| dc.date | 2008-04-18 | |
| dc.date.accessioned | 2026-07-07T09:33:28Z | |
| dc.date.available | 2026-07-07T09:33:28Z | |
| dc.description | We consider identifying codes in binary Hamming spaces F^n, i.e., in binary hypercubes. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let C be a subset of F^n. For any subset X of F^n, denote by I_r(X)=I_r(C;X) the set of elements of C within distance r from at least one x in X. Now C is called an (r,<= l)-identifying code if the sets I_r(X) are distinct for all subsets X of size at most l. We estimate the smallest size of such codes with fixed l and r/n converging to some number rho in (0,1). We further show the existence of such a code of size O(n^{3/2}) for every fixed l and r slightly less than n/2, and give for l=2 an explicit construction of small such codes for r the integer part of n/2-1 (the largest possible value). | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/0804.3029 | |
| dc.identifier | http://arxiv.org/abs/0804.3029 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/159144 | |
| dc.subject | Combinatorics | |
| dc.title | On the size of identifying codes in binary hypercubes | |
| dc.type | text |