Linear hereditary quasirandomness
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
- 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