The effect of induced subgraphs on quasi‐randomness

One of the main questions that arise when studying random and quasi‐random structures is which properties $ \cal P$ are such that any object that satisfies $ \cal P$ “behaves” like a truly random one. In the context of graphs, Chung, Graham, and Wilson (Combinatorica 9 (1989), 345–362) call a graph p‐quasi‐random if it satisfies a long list of the properties that hold in G ( n , p ) with high probability, such as edge distribution, spectral gap, cut size, and so on. Our main result here is that the following holds for any fixed graph H : if the distribution of induced copies of H in a graph G is close (in a well defined way) to the distribution we would expect to have in G ( n , p ), then G is either p ‐quasi‐random or p̄‐quasi‐random, where p̄ is the unique nontrivial solution of the polynomial equation x δ (1 − x ) 1−δ = p δ (1 − p ) 1−δ , with δ being the edge density of H . We thus infer that having the correct distribution of induced copies of any single graph H is enough to guarantee that a graph has the properties of a random one. The proof techniques we develop here, which combine probabilistic, algebraic, and combinatorial tools, may be of independent interest to the study of quasi‐random structures. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010