2025/04/24 by Kiril Bangachev, Bangachev, Kiril, Guy Bresler +1 · 1 citation
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Fault Detection and Control Systems #Probability (math.PR) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2504.17202
openalex publication_date 2025/04/24 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
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 \mathbbG(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 \mathbbG(n,1/2) and a stochastic block model \mathbbSBM. Quantitatively, this is related to approximately maximizing H \longrightarrow |Φ(H)|(1)/(|V(H)|), where Φ(H) is the Fourier coefficient of \mathbbSBM, 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 \mathbbSBM. We resolve the approximate maximization when \mathbbSBM 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) \mathbbSBM 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 \mathbbG(n,1/2) and \mathbbSBM, 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 \mathbbG(n,1/2) and any graphon if we also add triangles to A.