A universal bound for a covering in regular posets and its application to pool testing

Abstract:

Let V(n) be the set of all 2^{n} subsets of the set N_{n}={1,2,...,n} and V_{i}(n)={x∈V(n):|x|=i}. For a fixed i=1,...,n, consider a covering operator F : V_{i}(n)→ V(n) such that x⊆ F(x) for any x∈ V_{i}(n). Let C={F(x):x∈V_{i}(n)}. Using averaging and linear programming it is found an upper bound on the mean value |F(x)| over all x∈V_{i}(n) which is attained if and only if C is a Steiner S(i,{k,k+1},n) design with a specified distance distribution. A generalization of this result to the case of monotone left-regular n-posets is given. One of motivating applications is the problem of reconstructing an unknown binary vector x of length n using pool testing under the condition that the vectors x are distributed with probabilities p^{|x|}(1-p)^{n-|x|} where x∈V(n) denotes the indices of the ones (active items) in x. This improves upon an information theoretic bound for the minimum average number E(n,p) of tests to reconstruct an unknown x using two-stage pool testing and allows determination of the asymptotic behavior of E(n,p) up to a positive constant factor as n → ∞ under some restrictions upon p=p(n).

Keywords:

covering, poset, pool testing, Steiner system, universal bound.

Publication language:english

Research direction:

Mathematical problems and theory of numerical methods