Paperlane

no. 3 · Tuesday 27 October 2026

Quasirandomness from balanced and repeated subgraph counts

Guoqing Wang, Linlin Wang and Jun Yue

math.CO · v3

Abstract

Let $F$ be a graph on $m$ vertices with at least one edge, and let $0<p\le1$. We study when prescribed subgraph counts across disjoint vertex classes characterize $p$-quasirandom graph sequences. For positive multiplicities $\bm=(m_1,\ldots,m_r)$ summing to $m$ and positive class proportions $\balpha=(α_1,\ldots,α_r)$ with total at most one, we first classify symmetrized repeated-class counts for $r\ge3$: when $0<p<1$, they are forcing precisely if $e(F)>1$ or $\balpha\ne\bm/m$. We also obtain a complete classification of labelled transversal counts: for \rev{$0<p<1$, the only nonforcing profile is $F=K_2$ with class proportions $(1/2,1/2)$.} Together, these results settle conjectures of Janson and Sós [European J. Combin. 46 (2015)], Hatami, Hatami and Li [European J. Combin. 56 (2016)], and Janson [arXiv:2606.20186v1 (2026)]. The common ingredient is a balanced-count theorem for every graph with more than one edge, proved through a degree-sequence inequality, and its consequence of additive rigidity. Our arguments also determine the bad indices of the associated functional nullspaces and isolate the exceptional single-edge profiles. In particular, a non-divisibility theorem for grouped elementary symmetric polynomials excludes the higher-order obstructions in the repeated-class setting. In contrast, for two repeated classes and every $p\in(0,1)$, we construct nonquasirandom graph sequences satisfying the crossing-triangle counts at proportions $(1/3,2/3)$, with limiting edge density strictly below $p$. These counterexamples answer the crossing-triangle question negatively and show why the three-class assumption cannot be omitted.

fields
Combinatorics
pdf ↗ page arXiv:2610.28124 ↗