Quasirandomness from balanced and repeated subgraph counts
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality