Hereditary quasirandomness without regularity
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 p^e(H) |S|^v(H) ± δn^v(H) labeled copies of H, then G is quasirandom in the sense that every S ⊆ V (G) c...
| Những tác giả chính: | , , |
|---|---|
| Định dạng: | Journal article |
| Được phát hành: |
Cambridge University Press
2017
|
| Tóm tắt: | 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 p^e(H) |S|^v(H) ± δn^v(H) labeled copies of H, then G is quasirandom in the sense that every S ⊆ V (G) contains ½p|S|^2 ± ∊n^2 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. |
|---|