PC Seminar: Is it easier to count communities than to find them?

Abstract: 
We study the planted-dense-subgraph model where an Erdős–Rényi base graph is augmented by adding one or more `communities' - subsets of vertices with a higher-than-average connection probability between them. The detection problem is to distinguish between the vanilla Erdős–Rényi model and that with one or many planted communities and the recovery problem is to approximately recover the position of the community structure within the graph. A detection-recovery gap is known to occur, for some parameter combinations (sizes of structure, edge probabilities), we have fast algorithms to perform detection but recovery is not possible. We investigate something in-between: we want to infer some property of the community structure without needing to recover it. We say counting is the problem of distinguishing a single community from many. Our result is to show counting is no easier than detection. 
The combinatorics at play: let a=(a_H)_H and b=(b_H)_H be two sequences, indexed by graphs. We define a graph sequence r by setting the empty graph to have r-value 1, and via the following recursion r_G = a_G - \sum_H b_H r_{G\H} where the sum is over all non-empty subgraphs of G. Central to our proof is to show that the sequence r inherits properties of the sequences a and b. Loosely, in our context the sequence a (resp. b) encodes information of the probability space with many communities (resp. one community) and whether one can distinguish these two probability spaces is characterised by the value of the sum of squares of the r-values. 

Joint work with Cindy Rush, Alex Wein and Dana Yang.