Graph Quasirandomness for Hypothesis Testing of Stochastic Block Models

Kiril Bangachev, Guy Bresler

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 $\mat…