This is a continuation of our work on quasi-random graph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. One of the most important of these properties is that, for fixed v, every fixed sample graph L_v has the same frequency in G_n as in the p-random graph. (This holds for both induced and not necessarily induced containment.) In [9] we proved that, if the frequency of just one fixed L_v-as a not necessarily induced subgraph - in every 'large' induced subgraph F_h is contained in G_n is the same as for the random graphs, then (G_n) is quasi-random. Here we shall investigate the analogous problem for induced subgraphs L_v. In such cases (G_n) is not necessarily quasi-random. We shall prove, among other things, that, for every regular sample graph L_v, v ≥ 4, if the number of induced copies of L_v in every induced F_h is contained in G_n is asymptotically the same as in a p-random graph (up to an error term o (n~v)), then (G_n) is the union of (at most) two quasi-random graph sequences, with possibly distinct attached probabilities (assuming that p ∈(0,1), e(L_v) > 0, and L_v ≠ K_v). We conjecture the same conclusion for every L_v with v ≥ 4, i.e., even if we drop the assumption of regularity. We shall reduce the general problem to solving a system of polynomials. This gives a 'simple' algorithm to decide the problem for every given L_v.
展开▼
