Hereditary quasirandomness without regularity. (26th January 2017)

• Record Type: Journal Article
• Authors: CONLON, DAVID; FOX, JACOB; SUDAKOV, BENNY
• Is Part Of: Mathematical proceedings of the Cambridge Philosophical Society. Volume 164:Part 3(2018)
• Page Start: 385
• Page End: 399
• Publication Date: 2017-01-26
• Subjects: Mathematics -- Periodicals; 510.5
• DOI: 10.1017/S0305004116001055
• Languages: English
• ISSNs: 0305-0041

Abstract

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 p e(H) | S | v(H) ± δ n v(H) labelled copies of H, then G is quasirandom in the sense that every S ⊆ V ( G ) contains $\frac{1}{2}$ 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.