Premium
Quasi‐random classes of hypergraphs
Author(s) -
Chung Fan R. K.
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010401
Subject(s) - tuple , mathematics , combinatorics , random graph , hierarchy , binary number , equivalence (formal languages) , graph , hypergraph , discrete mathematics , computer science , arithmetic , economics , market economy
We investigate the relations among a number of different graph properties for k ‐uniformhypergraphs, 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.