Let V(n) be the set of all 2ⁿ 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).

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

Mathematical problems and theory of numerical methods