Quasirandomness in Hypergraphs

Abstract

A graph G is called quasirandom if it possesses typical properties of the corresponding random graph G(n, p) with the same edge density as G. A well-known theorem of Chung, Graham and Wilson states that, in fact, many such 'typical' properties are asymptotically equivalent and, thus, a graph G possessing one property immediately satisfies the others. In recent years, more quasirandom graph properties have been found and extensions to hypergraphs have been explored. For the latter, however, there exist several distinct notions of quasirandomness. A complete description of these notions has been provided recently by Towsner, who proved several central equivalences using an analytic framework. The purpose of this paper is to give short purely combinatorial proofs of most of Towsner's results.

Files

Additional details