PUB - Publikationen an der Universität Bielefeld

Already in his Lectures on Search [A. Rdnyi, Lectures on the theory of search, University of North Carolina, Chapel Hill, Institute of Statistics, Mimeo Series No. 6007, 1969. [11]] Renyi suggested to consider a search problem, where an unknown x is an element of X = {1, 2, ..., n} is to be found by asking for containment in a minimal number m(n, k) of subsets A(1),...,A(m) with the restrictions vertical bar A(i)vertical bar <= k < n/2 for i = 1, 2,..., m. Katona gave in 1966 the lower bound m(n, k) >= log n/h (k/n) in terms of binary entropy and the upper bound m(n, k) <= inverted right perpendicular log n + 1) / log n/k inverted left perpendicular which was improved by Wegener in 1979 to m(n, k) <= inverted right perpendicular log n / log n/k inverted left perpendicular (inverted right perpendicular n/k inverted left perpendicular - 1). We prove here for k=pn that m (n, k)=log n+o(log n)/h (p), that is, ratewise optimality of the entropy bound: lim(n ->infinity) m (n, pn)/logn = 1/h(p). Actually this work was motivated by a more recent study of Karpovsky, Chakrabarty, Levitin and Avresky of a problem on fault diagnosis in hypercubes, which amounts to finding the minimal number M(n, r) of Hamming balls of radius r = rho n with rho <= 1/2 in the Hamming space H-n = {0, 1}(n), which separate the vertices. Their bounds on M(n, r) are far from being optimal. We establish bounds implying lim(n ->infinity) 1/n log M(n, r) = 1 - h(rho). However, it must be emphasized that the methods of prove for our two upper bounds are quite different. (C) 2007 Elsevier B.V. All rights reserved.