zbMATH — the first resource for mathematics

Quasi-random graphs. (English) Zbl 0715.05057
From the authors’ abstract: “We introduce a large equivalence class of graph properties, all of which are shared by so-called random graphs. Unlike random graphs, however, it is often relatively easy to verify that a particular family of graphs possesses some property in this class.”
Reviewer: E.M.Palmer

05C80 Random graphs (graph-theoretic aspects)
05C99 Graph theory
Full Text: DOI
[1] N. Alon andF. R. K. Chung, Explicit constructions of linear-sized tolerant networksDiscrete Math.,72 (1988), 15–20. · Zbl 0657.05068
[2] B. Bollobás,Random Graphs, Academic Press, New York, 1985.
[3] B. Bollobás andA. Thomason, Graphs which contain all small graphs,European J. Comb. 2 (1981), 13–15. · Zbl 0471.05037
[4] D. A. Burgess, On character sums and primitive roots,Proc. London Math. Soc. 12 (1962), 179–192. · Zbl 0106.04003
[5] P.Erdos and A.Hajnal, On spanned subgraphs of graphs,Beitrage zur Graphentheorie und deren Anwendungen, Kolloq. Oberhof (DDR), (1977), 80–96.
[6] P. Erdos andJ. Spencer,Probabilistic Methods in Combinatorics, Akadémiai Kiadó, Budapest, 1974.
[7] P. Frankl andR. L. Graham, Intersection theorems for vector spaces,European J. Comb. 6 (1985), 183–187. · Zbl 0577.15002
[8] P.Frankl, V.Rödl and R. M.Wilson, The number of submatrices of given type in a Hadamard matrix and related results (to appear). · Zbl 0658.05015
[9] P. Frankl andR. M. Wilson, Intersection theorems with geometric consequences,Combinatorica 1 (1981), 357–368. · Zbl 0498.05048
[10] Z. Füredi andJ. Komlós, The eigenvalues of random symmetric matrices,Combinatorica 1 (1981), 233–241. · Zbl 0494.15010
[11] F. R. Gantmacher,Matrix Theory, Vol. 1, Chelsea, New York, 1977.
[12] R. L. Graham andJ. H. Spencer, A constructive solution to a tournament problem,Canad. Math. Bull. 14 (1971), 45–48. · Zbl 0209.55804
[13] F.Juhász, On the spectrum of a random graph,Colloq. Math. Soc. János Bolyai 25,Algebraic Methods in Graph Theory, Szeged (1978), 313–316.
[14] H. L. Montgomery, Topics in Multiplicative Number Theory,Lecture Notes in Math. 227, Springer-Verlag, New York, 1971. · Zbl 0216.03501
[15] E. M. Palmer,Graphical Evolution, Wiley, New York, 1985. · Zbl 0566.05002
[16] V. Rödl, On the universality of graphs with uniformly distributed edges,Discrete Math. 59 (1986), 125–134. · Zbl 0619.05035
[17] A. Thomason, Random graphs, strongly regular graphs and pseudo-random graphs, in Surveys in Combinatorics 1987 (C. Whitehead, ed.)LMS Lecture Notes Series 123, Cambridge Univ. Press, Cambridge, (1987), 173–196. · Zbl 0672.05068
[18] A.Thomason, Random graphs, strongly regular graphs and pseudo-random graphs, in Surveys · Zbl 0672.05068
[19] A.Thomason, Pseudo-random graphs, in Proceedings of Random Graphs, Poznań 1985 (M. Karonski, ed.)Annals of Discrete Math. 33 (1987), 307–331.
[20] A.Weil, Sur les courbes algébrique et les variétés qui s’en déduisent,Actualités Sci. Ind. No. 1041 (1948). · Zbl 0036.16001
[21] R. M. Wilson, Cyclotomy and difference families in abelian groups,J. Number Th. 4 (1972), 17–47. · Zbl 0259.05011
[22] R. M.Wilson, Constructions and uses of pairwise balanced designs, in Combinatorics (M. Hall, Jr. and J. H. van Lint, eds.),Math. Centre Tracts 55, Amsterdam (1974), 18–41. · Zbl 0312.05010
[23] F. R. K.Chung and R. L.Graham, Quasi-random hypergraphs,to appear. · Zbl 0708.05044
[24] S. W.Graham and C.Ringrose,to appear.
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.