Linear hereditary quasirandomness

arXiv:2610.39317 · math.CO · Submitted 2026-10-29 · Read on arXiv

math.CO

Submitted: 2026-10-29

Updated: 2026-10-29

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

The gist: Conlon, Fox and Sudakov (Math.

Abstract

Conlon, Fox and Sudakov (Math. Proc. Cambridge Philos. Soc. 164 (2018), 385--399) conjectured that hereditary subgraph counts force quasirandomness with linear dependence on the counting error. We prove this for every graph containing an edge. Let H have r vertices and m at least1 edges, and fix p in(0,1). If every subset S of an n-vertex graph G contains p mS r plus or minusδn r labelled injective copies of H, then e G(A,B)-pAB at most C H,pδn squared for all A,B V(G), where e G(A,B) counts ordered adjacent pairs. The proof extracts averaged rooted counts and represents each nonlinear term by a linear map in one selected edge factor. Composing two such maps gives an edge substitution with a superlinear cut-norm bound. A separate star expansion gives stronger local estimates for triangle-free graphs. The linear order is best possible even when 2e(G)/n 2=p+O(n-2).

Related papers