Article contents
Hereditary quasirandomness without regularity
Published online by Cambridge University Press: 26 January 2017
Abstract
A result of Simonovits and Sós states that for any fixed graph H and any ε > 0 there exists δ > 0 such that if G is an n-vertex graph with the property that every S ⊆ V(G) contains pe(H) |S|v(H) ± δ nv(H) labelled copies of H, then G is quasirandom in the sense that every S ⊆ V(G) contains $\frac{1}{2}$p|S|2± ε n2 edges. The original proof of this result makes heavy use of the regularity lemma, resulting in a bound on δ−1 which is a tower of twos of height polynomial in ε−1. We give an alternative proof of this theorem which avoids the regularity lemma and shows that δ may be taken to be linear in ε when H is a clique and polynomial in ε for general H. This answers a problem raised by Simonovits and Sós.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 164 , Issue 3 , May 2018 , pp. 385 - 399
- Copyright
- Copyright © Cambridge Philosophical Society 2017
References
REFERENCES
- 4
- Cited by