Generalized quasirandom graphs. (English) Zbl 1127.05094

Summary: We prove that if a sequence of graphs has (asymptotically) the same distribution of small subgraphs as a generalized random graph modeled on a fixed weighted graph \(H\), then these graphs have a structure that is asymptotically the same as the structure of \(H\). Furthermore, it suffices to require this for a finite number of subgraphs, whose number and size is bounded by a function of \(|V(H)|\).


05C80 Random graphs (graph-theoretic aspects)
81Q10 Selfadjoint operator theory in quantum theory, including spectral analysis
Full Text: DOI Link


[1] Borgs, C.; Chayes, J.T.; Lovász, L.; Sós, V.T.; Vesztergombi, K., Counting graph homomorphisms, (), 315-371 · Zbl 1129.05050
[2] C. Borgs, J. Chayes, L. Lovász, V.T. Sós, K. Vesztergombi, Convergent graph sequences I: Subgraph frequencies, metric properties, and testing; Convergent graph sequences II: Multiway cuts and statistical physics, Manuscript
[3] Chung, F.R.; Graham, R.L.; Wilson, R.K., Quasi-random graphs, Combinatorica, 9, 345-362, (1989) · Zbl 0715.05057
[4] Freedman, M.; Lovász, L.; Schrijver, A., Reflection positivity, rank connectivity, and homomorphisms of graphs, J. amer. math. soc., 20, 37-51, (2007) · Zbl 1107.05089
[5] Lovász, L., The rank of connection matrices and the dimension of graph algebras, European J. combin., 27, 962-970, (2006) · Zbl 1088.05052
[6] Lovász, L.; Szegedy, B., Contractors and connectors of graph algebras, J. combin. theory ser. B, 96, 933-957, (2006) · Zbl 1113.05092
[7] Simonovits, M.; Sós, V.T., Szemerédi’s partition and quasirandomness, Random structures algorithms, 2, 1-10, (1991) · Zbl 0766.05080
[8] Simonovits, M.; Sós, V.T., Hereditary extended properties, quasi-random graphs and induced subgraphs, Combin. probab. comput., 12, 319-344, (2003) · Zbl 1043.05107
[9] Simonovits, M.; Sós, V.T., Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs, Combinatorica, 17, 577-596, (1997) · Zbl 0906.05066
[10] Thomason, A., Pseudorandom graphs, (), 307-331
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.