zbMATH — the first resource for mathematics

Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets. (English) Zbl 1224.05476
A graph \(G(n)\) is \(p\)-quasi-random if it behaves like the random graph \(G(n,p)\) for sufficiently large \(n\) and any \(0<p<1\). It is proved that \(G(n)\) is \(p\)-quasi-random if, for every fixed graph \(H\) and every fixed proportion \(0<w<1\), the subgraph of \(G(n)\) induced by any vertex subset of size \(wn\) contains as many copies of \(H\) as would be expected in \(G(n,p)\).

05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI arXiv
[1] F. R. K. Chung and R. L. Graham: Quasi-random set systems, Journal of the AMS 4 (1991), 151–196. · Zbl 0761.05072
[2] F. R. K. Chung and R. L. Graham: Quasi-random tournaments, Journal of Graph Theory 15 (1991), 173–198. · Zbl 0728.05025
[3] F. R. K. Chung and R. L. Graham: Quasi-random hypergraphs, Random Structures and Algorithms 1 (1990), 105–124. · Zbl 0708.05044
[4] F. R. K. Chung, R. L. Graham and R. M. Wilson: Quasi-random graphs, Combinatorica 9(4) (1989), 345–362. · Zbl 0715.05057
[5] T. Gowers: Quasirandom groups, Combinatorics, Probability and Computing 17 (2008), 363–387. · Zbl 1191.20016
[6] M. Krivelevich and B. Sudakov: Pseudo-random graphs, in: More sets, graphs and numbers (E. Györi, G. O. H. Katona and L. Lovász, eds.), Bolyai Society Mathematical Studies Vol. 15 (2006), 199–262. · Zbl 1098.05075
[7] L. Lovász and V. T. Sós: Generalized quasirandom graphs, Journal of Combinatorial Theory Series B 98 (2008), 146–163. · Zbl 1127.05094
[8] A. Shapira: Quasi-randomness and the distribution of copies of a fixed graph, Combinatorica 28(6) (2008), 735–745. · Zbl 1196.05090
[9] 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
[10] 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.
[11] 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
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.