  In this paper, an information theoretic analysis on non-adaptive group
testing schemes based on sparse pooling graphs is presented. The binary status
of the objects to be tested are modeled by i.i.d. Bernoulli random variables
with probability p. An (l, r, n)-regular pooling graph is a bipartite graph
with left node degree l and right node degree r, where n is the number of left
nodes. Two scenarios are considered: a noiseless setting and a noisy one. The
main contributions of this paper are direct part theorems that give conditions
for the existence of an estimator achieving arbitrary small estimation error
probability. The direct part theorems are proved by averaging an upper bound on
estimation error probability of the typical set estimator over an (l,r,
n)-regular pooling graph ensemble. Numerical results indicate sharp threshold
behaviors in the asymptotic regime.
