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 $\mathbb{ 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 $\mathbb{ G}(n,1/2)$ and a stochastic block model $\mathbb{ SBM}.$ Quantitatively, this is related to approximately maximizing $H \longrightarrow |\Phi(H)|^{ \frac{ 1}{ |\mathsf{ V}(H)|}},$ where $\Phi(H)$ is the Fourier coefficient of $\mathbb{ 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 $\mathbb{ SBM}.$ We resolve the approximate maximization when $\mathbb{ 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) $\mathbb{ SBM}$ has two communities. In each of these cases, we show that there is an approximate maximizer of $|\Phi(H)|^{ \frac{ 1}{ |\mathsf{ V}(H)|}}$ in the set $\mathsf{ A} = \{ \text{ stars, 4-cycle}\}.$ This implies that if there exists a constant-degree polynomial test distinguishing $\mathbb{ G}(n,1/2)$ and $\mathbb{ SBM},$ then the two distributions can also be distinguished via the signed count of some graph in $\mathsf{ A}.$ We conjecture that the same holds true for distinguishing $\mathbb{ G}(n,1/2)$ and any graphon if we also add triangles to $\mathsf{ A}.$
Categories: math.ST math.CO math.PR stat.TH