Пусть V(n) - множество всех 2ⁿ подмножеств N_n={1,2,...,n} и V_i(n)={x∈V(n):|x|=i}. При фиксированном i=1,...,n, рассмотрим оператор покрытия F : Vⁱ(n)→ V(n) такой, что x⊆ F(x) для любого x∈V_i(n). Пусть C={F(x):x∈V_i(n)}. С помощью усреднения и линейного программирования найдена верхняя граница для среднего значения величины |F(x)| по всем x∈V_i(n) которая достигается тогда и только тогда, когда C образует систему Штейнера S(i,{k,k+1},n) с определенным распределением весов кодовых слов. Приводится обобщение этого результата на регулярные слева частично упорядоченные множества с n элементами. Одним из мотивирующих приложений является задача восстановления неизвестного двоичного вектора x длины n с помощью группового тестирования при условии, что векторы x рапределены с вероятностями p^|x|(1-p)^n-|x|, где x∈V(n) задает места единиц (активных объектов) в x. Полученная граница улучшает теоретико-информационную границу для минимального среднего числа E(n,p) тестов для восстановления неизвестного вектора x с помощью двухуровнего группового тестирования и позволяет определить с точностью до константы асимптотическое поведение E(n,p) при некоторых ограничениях на p=p(n), когда n → ∞.

покрытие, частично упорядоченные множества, групповое тестирование, системы Штейнера, универсальная граница.

Математические вопросы и теория численных методов