Balanced subgraph counts and quasirandomness: a proof of the Janson--Sós conjecture

Source abstract

For $0<p\leq1$, a graph sequence is $p$-quasirandom if every fixed finite simple graph $H$ has limiting labelled subgraph density $p^{|E(H)|}$. Janson and Sós [\emph{European J. Combin.} (2015)] conjectured that, for every finite simple graph $F$ with at least two edges, $p$-quasirandomness is characterized by the random-graph asymptotics of the symmetrized counts of copies of $F$ across every balanced partition into $|V(F)|$ classes. In this paper, we prove this conjecture for all such $F$, including those with isolated vertices.