zbMATH — the first resource for mathematics

Quasi-randomness and the distribution of copies of a fixed graph. (English) Zbl 1196.05090
The notion of quasi-randomness is due to 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 F. R. K. Chung, R. L. Graham and 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\).
M. Simonovits and 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 D. H. Gottlieb [Proc. Am. Math. Soc. 17, 1233–1237 (1966; Zbl 0146.01302)] on the rank of incidence matrices.

05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
Full Text: DOI
[1] D. de Caen: A note on the ranks of set-inclusion matrices, Electr. J. Comb. 8(1) (2001), #N5. · Zbl 0976.15003
[2] F. R. K. Chung and R. L. Graham: Quasi-random set systems, J. of the AMS 4 (1991), 151–196. · Zbl 0761.05072
[3] F. R. K. Chung and R. L. Graham: Quasi-random tournaments, J. of Graph Theory 15 (1991), 173–198. · Zbl 0728.05025
[4] F. R. K. Chung and R. L. Graham: Quasi-random hypergraphs, Random Structures and Algorithms 1 (1990), 105–124. · Zbl 0708.05044
[5] F. R. K. Chung and R. L. Graham: Maximum cuts and quasi-random graphs, in: Random Graphs (Poznań Conf., 1989), Wiley-Intersci. Publ. vol. 2, 23–33.
[6] F. R. K. Chung, R. L. Graham and R. M. Wilson: Quasi-random graphs, Combinatorica 9(4) (1989), 345–362. · Zbl 0715.05057
[7] D. H. Gottlieb: A class of incidence matrices, Proc. Amer. Math. Soc. 17 (1966), 1233–1237. · Zbl 0146.01302
[8] T. Gowers: Quasirandom groups, manuscript, 2006. · Zbl 1191.20016
[9] L. Lovász and V. T. Sós: Generalized quasirandom graphs, Journal of Combinatorial Theory Series B 98 (2008), 146–163. · Zbl 1127.05094
[10] M. Simonovits and V. T. Sós: Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs; Combinatorica 17(4) (1997), 577–596. · Zbl 0906.05066
[11] A. Thomason: Pseudo-random graphs, in: Proc. of Random Graphs, Poznań (1985), M. Karoński, ed., Annals of Discrete Math. 33 (North Holland, 1987), 307–331.
[12] A. Thomason: Random graphs, strongly regular graphs and pseudo-random graphs; in: Surveys in Combinatorics, C. Whitehead, ed., LMS Lecture Note Series 123 (1987), 173–195. · Zbl 0672.05068
[13] R. M. Wilson: A diagonal form for the incidence matrix of t-subsets vs. k-subsets, European J. Combin. 11 (1990), 609–615. · Zbl 0747.05016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.