Quasirandomness from balanced and repeated subgraph counts

arXiv:2610.28124 · math.CO · Submitted 2026-10-20 · Read on arXiv

math.CO

Submitted: 2026-10-20

Updated: 2026-10-26

License: http://creativecommons.org/licenses/by/4.0/

The gist: Let F be a graph on m vertices with at least one edge, and let 0<p at most1.

Terminology

Abstract

Let F be a graph on m vertices with at least one edge, and let 0<p at most1. We study when prescribed subgraph counts across disjoint vertex classes characterize p-quasirandom graph sequences. For positive multiplicities =(m 1,,m r) summing to m and positive class proportions =(α 1,,α r) with total at most one, we first classify symmetrized repeated-class counts for r at least3: when 0<p<1, they are forcing precisely if e(F)>1 or not equal to/m. We also obtain a complete classification of labelled transversal counts: for 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.

Sources

Related papers