On the size of identifying codes in binary hypercubes

: Janson S, Laihonen T

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2009

: Journal of Combinatorial Theory, Series A

: JOURNAL OF COMBINATORIAL THEORY SERIES A

: J COMB THEORY A

: 116

: 5

: 1087

: 1096

: 10

: 0097-3165

DOI: https://doi.org/10.1016/j.jcta.2009.02.004

where r = left perpendicular rho nright perpendicular, rho epsilon [0, 1) and h(x) is the binary entropy function. In this paper, we prove that this result holds for any fixed l >= 1 when rho epsilon [0, 1/2). We also show that M(r)((<= l))(n) = O(n(3/2)) for every fixed l and r slightly less than n/2, and give an explicit construction of small (r, <= 2)-identifying codes for r = left perpendicularn/2right perpendicular - 1. (C) 2009 Elsevier Inc. All rights reserved.