  This paper studies structure detection problems in high temperature
ferromagnetic (positive interaction only) Ising models. The goal is to
distinguish whether the underlying graph is empty, i.e., the model consists of
independent Rademacher variables, versus the alternative that the underlying
graph contains a subgraph of a certain structure. We give matching upper and
lower minimax bounds under which testing this problem is possible/impossible
respectively. Our results reveal that a key quantity called graph arboricity
drives the testability of the problem. On the computational front, under a
conjecture of the computational hardness of sparse principal component
analysis, we prove that, unless the signal is strong enough, there are no
polynomial time tests which are capable of testing this problem. In order to
prove this result we exhibit a way to give sharp inequalities for the even
moments of sums of i.i.d. Rademacher random variables which may be of
independent interest.
