Linear hereditary quasirandomness
Abstract
Conlon, Fox and Sudakov (\emph{Math. Proc. Cambridge Philos. Soc.} \textbf{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≥1 edges, and fix p∈(0,1). If every subset S of an n-vertex graph G contains pm|S|r±δnr labelled injective copies of H, then lvert eG(A,B)−p|A||B|rvert≤ CH,pδn2 for all A,B⊆ V(G), where eG(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)/n2=p+O(n−2).
Related
- Tests of graph homogeneity, subgraph counts, and quasirandomness
- Quasirandomness from balanced and repeated subgraph counts
- Hereditary Approximation under Hilbertian Extension
- A hereditary theorem for rigid and pseudorigid components of Lusztig's nilpotent varieties in type A
- Hereditary lowerability of diagonal entropy scales
BibTeX
@misc{yue2026linear,
title = {{Linear hereditary quasirandomness}},
author = {Jun Yue},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39317},
eprint = {2610.39317},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39317},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Linear hereditary quasirandomness
AU - Jun Yue
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39317
UR - https://arxiv.org/abs/2610.39317
AB - Conlon, Fox and Sudakov (\emph{Math. Proc. Cambridge Philos. Soc.} \textbf{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≥1 edges, and fix p∈(0,1). If every subset S of an n-vertex graph G contains p^m|S|^r±δn^r labelled injective copies of H, then lvert e_G(A,B)−p|A||B|rvert≤ C_H,pδn^2 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).
ER -