Quasirandomness from balanced and repeated subgraph counts
Abstract
Let F be a graph on m vertices with at least one edge, and let 0<p≤1. We study when prescribed subgraph counts across disjoint vertex classes characterize p-quasirandom graph sequences. For positive multiplicities =(m1,…,mr) summing to m and positive class proportions balpha=(α1,…,αr) with total at most one, we first classify symmetrized repeated-class counts for r≥3: when 0<p<1, they are forcing precisely if e(F)>1 or balpha≠/m. We also obtain a complete classification of labelled transversal counts: for \rev{0<p<1, the only nonforcing profile is F=K2 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∈(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.
Related
- Tests of graph homogeneity, subgraph counts, and quasirandomness
- Normal approximation for subgraph counts in random intersection graphs: the case of cliques
- Exact Realization of Edge and Induced Three-Vertex Subgraph Counts
- Fluctuations of subgraph counts in exponential random graphs
- Transposition Cayley Spectra and Subgraph Counts
BibTeX
@misc{wang2026quasirandomness,
title = {{Quasirandomness from balanced and repeated subgraph counts}},
author = {Guoqing Wang and Linlin Wang and Jun Yue},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28124},
eprint = {2610.28124},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28124},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quasirandomness from balanced and repeated subgraph counts
AU - Guoqing Wang
AU - Linlin Wang
AU - Jun Yue
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.28124
UR - https://arxiv.org/abs/2610.28124
AB - Let F be a graph on m vertices with at least one edge, and let 0<p≤1. 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 balpha=(α_1,…,α_r) with total at most one, we first classify symmetrized repeated-class counts for r≥3: when 0<p<1, they are forcing precisely if e(F)>1 or balpha≠/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∈(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.
ER -