Quasi-randomness and the distribution of copies of a fixed graph (Q1046741): Difference between revisions

The notion of quasi-randomness is due to \textit{A. Thomason} [Surveys in combinatorics 1987, Pap. 11th Br. Combin. Conf., London/Engl. 1987, Lond. Math. Soc. Lect. Note Ser. 123, 173--195 (1987; Zbl 0672.05068)]. By the subsequent work of \textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, No. 4, 345--362 (1989; Zbl 0715.05057)] it turned out that a sequence of graphs is quasi-random if it exhibits some behavior of random graph properties asymptotically, and in fact a number of equivalent properties ensure this. For graphs \(H\) and \(G\) and \(U \subset V(G)\), let \(H(U)\) be the number of labeled copies of \(H\) spanned by \(U\). Two properties that Chung et al gave were \({\mathcal P}_1(t)\) and \({\mathcal P}_2\). \textit{M. Simonovits} and \textit{V. T. Sós} [Combinatorica 17, No. 4, 577--596 (1997; Zbl 0906.05066)] gave a different notion, which allowed a generalization of these results. For a fixed graph \(H\) on \(h\) vertices, the sequence \(G_n\) has the property \({\mathcal P}_H\) if (1) \(H(U)=p^{e(H)}| U| ^h+o(n^h)\) for all \(U \subset V(G_n)\). They showed that for any fixed \(H\) with \(e(H) >0\), property \(\mathcal P_H\) is quasi-random. However, it was left open if one really needs the property \({\mathcal P}_H\) for all \(U \subset V(G_n)\), and they asked if less assumptions on \(U\) was enough for quasi-randomness. The author of this paper shows that the quasi-randomness of a sequence \(G_n\) follows if for a fixed, non-empty graph \(H\) (1) holds for \(U \subset V(G_n)\), \(| U| =\lfloor n/(h+1) \rfloor\), where \(h=| V(H)| \). The proof utilizes simple counting arguments and an old result of \textit{D. H. Gottlieb} [Proc. Am. Math. Soc. 17, 1233--1237 (1966; Zbl 0146.01302)] on the rank of incidence matrices.