Quasirandomness in Hypergraphs
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.
© The authors. Released under the CC BY-ND license (International 4.0). Submitted: Dec 12, 2017; accepted Jul 24, 2018; published: Aug 24, 2018. The second author was supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. The third author was supported by the FONDECYT Iniciación grant 11150913 and by Millenium Nucleus Information and Coordination in Networks. The fourth author was supported by DFG grant PE 2299/1-1. The fifth author was supported by ERC Consolidator Grant 724903. We are indebted to the anonymous referee for their careful review.
Published - EJC25.3.34.pdf