Thomason and Chung, Graham, and Wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a deterministic sense. Their concepts of quasi-randomness match the notion of ε-regularity from the earlier Szemeredi regularity lemma. In contrast, there exists no 'natural' hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors.
展开▼