×

Quasi-random classes of hypergraphs. (English) Zbl 0739.05066

Summary: We investigate the relations among a number of different graph properties for \(k\)-uniform-hypergraphs, which are shared by random hypergraphs. Various graph properties form equivalence classes which in turn constitute a natural hierarchy. The analogues for binary functions on \(k\)-tuples and for hypergraphs with small density are also considered. Several classes are related to communication complexity and expander graphs.

MSC:

05C65 Hypergraphs
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , On notions of information transfer in VLSI circuits, Proc. 15th Symposium on Theory of Computing, 133–139 (1983).
[2] Ajtai, Combinatorica 3 (1983)
[3] Alon, Discrete Math. 72 pp 15– (1988)
[4] , and , Complexity classes in communication complexity theory, Foundation of Computer Science, 337–347 (1986).
[5] , and , Multi-party protocols and logspace-hard pseudorandom sequences, Twenty-First Symposium on the Theory of Computing, 1–11 (1989).
[6] Burgess, Proc. London Math. Soc. 12 pp 179– (1962)
[7] , and , Multiparty protocols, Foundation of Computer Science, 94–99 (1983).
[8] Chung, J. AMS 2 pp 187– (1989)
[9] Chung, Random Struct. Algorithms 1 pp 105– (1990)
[10] and , Maximum cuts and quasi-random graphs, preprint.
[11] and , Quasi-random set systems, preprint.
[12] Chung, Combinatorica 9 pp 345– (1989)
[13] and , On spanned subgraphs of graphs, Beitrage zur Graphentheorie und deren Anwendungen, Kolloq. Oberhof (DDR), 80–96 (1977).
[14] Erdös, Combinatorica 2 pp 289– (1982)
[15] Erdös, Networks 1 pp 379– (1972)
[16] and , Probabilistic Methods in Combinatorics, Akadémiai Kiadó, Budapest, 1974.
[17] and (personal communication).
[18] Frankl, The number of submatrices of given type in a Hadamard matrix and related results · Zbl 0658.05015
[19] Graham, Can. Math. Bull. 14 pp 45– (1971) · Zbl 0209.55804 · doi:10.4153/CMB-1971-007-1
[20] Haviland, Discrete Math. 75 pp 255– (1989)
[21] Katz, J. AMS 2 pp 197– (1989)
[22] and , Finite Fields, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, England, 1984.
[23] Communication complexity, in Paths, Flows and VLSI Design, Proceedings of the Bonn Conference (1989).
[24] Margulis, Prob. Per. Infor. 9 pp 71– (1973)
[25] English translation in Problems of Infor. Trans., 325–332 (1975).
[26] Rödl, Discrete Math. 59 pp 125– (1986)
[27] Linear Representations of Finite Groups, Springer-Verlag, New York, 1982.
[28] and , Szemeréedi partition and quasi-randomness, preprint.
[29] Expanders, randomness, or time versus space, JCSS, 379–383 (1988). · Zbl 0652.68050
[30] 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.
[31] Thomason, Ann. Discrete Math. 33 pp 307– (1987)
[32] Towards a strong communication complexity theory of generating quasi-random sequences from two communicating semirandom sources, Proc. 17th STOC, 366–378 (1985).
[33] Weil, Actualités Sci. Ind. 1041 (1948)
[34] Wilson, J. Number Th. 4 pp 17– (1972)
[35] Wilson, Math. Centre Tracts 55 pp 18– (1974)
[36] Some complexity questions related to distributed computing, Proc. 11th STOC, 209–312 (1979).
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.