Detection theory on random graphs

This paper presents some results in a theory of detection on random graphs. An Erdos-Renyi random graph serves as our noise model. Signals are represented by specific types of subgraphs embedded in the noise graph or other known structural characteristics. The paper begins with some known results about the expected number of subgraphs of a specific type in a random graph. This result is used to convince the reader of his likely poor intuition on which types of subgraphs will commonly appear in the noise graph. A detection problem called the prescribed subgraph problem is presented. A closed form calculation of the optimal detection statistic, i.e., the likelihood ratio, is the main result. Other results on detection theory for Erdos-Renyi random graphs are presented along with some results for other random graph models.