Certain statistical problems on graphs (Q2266318)

The problem of existence of consistent tests, solved in this paper, has arisen, as the author says, in connection with problems of cluster analysis when statistical methods are used to establish significance of the selected clusters. There are considered two hypotheses \(H_ 0\) and \(H_ k\) defined as follows. Let \(G_ n\) be the class of all graphs with n vertices \(X_ n=(x_ 1,...,x_ n)\). For all \(A\subseteq X_ n\) a special, in a certain sense independent, probability measure \(P_ A\) on \(G_ n\) is defined such that \(P_ A(G=(X_ n,E))\) depends only on a number of edges from E which are incidental to elements of A. Testing the null hypothesis \(H_ 0: A=\emptyset\) against the alternative \(H_ k:| A| =k\) is considered. There are three theorems proven in the paper specifying sufficient conditions for situations when corresponding consistent tests do or do not exist.