Total: 1
The celebrated theorem of Chung, Graham, and Wilson on quasirandom graphs implies that if the 4-cycle and edge counts in a graph G are both close to their typical number in G(n,1/2), then this also holds for the counts of subgraphs isomorphic to H for any H of constant size. We aim to prove a similar statement where the notion of close is whether the given (signed) subgraph count can be used as a test between G(n,1/2) and a stochastic block model SBM. Quantitatively, this is related to approximately maximizing H⟶|Φ(H)|1|V(H)|, where Φ(H) is the Fourier coefficient of SBM, indexed by subgraph H. This formulation turns out to be equivalent to approximately maximizing the partition function of a spin model over alphabet equal to the community labels in SBM. We resolve the approximate maximization when SBM satisfies one of four conditions: 1) the probability of an edge between any two vertices in different communities is exactly 1/2; 2) the probability of an edge between two vertices from any two communities is at least 1/2 (this case is also covered in a recent work of Yu, Zadik, and Zhang); 3) the probability of belonging to any given community is at least c for some universal constant c>0; 4) SBM has two communities. In each of these cases, we show that there is an approximate maximizer of |Φ(H)|1|V(H)| in the set A={stars, 4-cycle}. This implies that if there exists a constant-degree polynomial test distinguishing G(n,1/2) and SBM, then the two distributions can also be distinguished via the signed count of some graph in A. We conjecture that the same holds true for distinguishing G(n,1/2) and any graphon if we also add triangles to A.