  We consider the hypothesis testing problem of deciding whether an observed
high-dimensional vector has independent normal components or, alternatively, if
it has a small subset of correlated components. The correlated components may
have a certain combinatorial structure known to the statistician. We establish
upper and lower bounds for the worst-case (minimax) risk in terms of the size
of the correlated subset, the level of correlation, and the structure of the
class of possibly correlated sets. We show that some simple tests have
near-optimal performance in many cases, while the generalized likelihood ratio
test is suboptimal in some important cases.
