Hereditary quasirandomness without regularity

Abstract: A result of Simonovits and S'os states that for any fixed graph

H

and any

e p s i l o n > 0

there exists

d e l t a > 0

such that if

G

is an

n

-vertex graph with the property that every

S s u b s e t e q V (G)

contains

p^{e (H)} | S |^{v (H)} p m d e l t a n^{v (H)}

labeled copies of

H

, then

G

is quasirandom in the sense that every

S s u b s e t e q V (G)

contains

f r a c 12 p | S |^{2} p m e p s i l o n n^{2}

edges. The original proof of this result makes heavy use of the regularity lemma, resulting in a bound on

d e l t a^{- 1}

which is a tower of twos of height polynomial in

e p s i l o n^{- 1}

. We give an alternative proof of this theorem which avoids the regularity lemma and shows that

d e l t a

may be taken to be linear in

e p s i l o n

when

H

is a clique and polynomial in

e p s i l o n

for general

H

. This answers a problem raised by Simonovits and S'os.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Hereditary quasirandomness without regularity