zbMATH — the first resource for mathematics

Quasi-random hypergraphs. (English) Zbl 0708.05044
Summary: We introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi-random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of ways.

05C65 Hypergraphs
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI
[1] Chung, Combinatorica (1989)
[2] Random Graphs, Academic, New York, 1985.
[3] Erdös, Combinatorica 2 pp 289– (1982)
[4] Rödl, Discrete Math. 59 pp 125– (1986)
[5] , and , Concrete Mathematics, Addison-Wesley, Reading, MA, 1989.
[6] Bollobás, European J. Comb. 2 pp 13– (1981) · Zbl 0471.05037
[7] Burgess, Proc. London Math. Soc. 12 pp 179– (1962)
[8] Sur les courbes algébrique et les variétés qui s’en déduisent. Actualités Sci. Ind., No. 1041 (1948).
[9] Graham, Canad. Math. Bull. 14 pp 45– (1971) · Zbl 0209.55804
[10] Chung, On graphs with missing prescribed induced subgraphs
[11] and (personal communication).
[12] Random graphs, strongly regular graphs and pseudo-random graphs, in Surveys in Combinatorics 1987 (Ed.), LMS Lecture Notes Series 123, Cambridge University Press, Cambridge, England 1987, pp. 173–196.
[13] Pseudo-random graphs, in Proceedings of Random Graphs, Poznán, Poland, 1985 (M. Karonski, Ed.), Annals of Discrete Math., 33 307–331 (1987).
[14] Chung, Quasi-random classes for hypergraphs · Zbl 0739.05066
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.