Quasi-randomness Is Determined by theDistribution of Copies of a Fixed Graph in Equicardinal Large Sets

摘要

For every fixed graph H and every fixed 0 < α < 1, we show that if a graph G has the property that all subsets of size an contain the "correct" number of copies of H one would expect to find in the random graph G(n,p) then G behaves like the random graph G(n,p); that is, it is p-quasi-random in the sense of Chung, Graham, and Wilson [4]. This solves a conjecture raised by Shapira [8] and solves in a strong sense an open problem of Simonovits and Sos [9].