A Caltech Library Service

Quasirandomness in Hypergraphs

Aigner-Horev, Elad and Conlon, David and Hàn, Hiệp and Person, Yury and Schacht, Mathias (2018) Quasirandomness in Hypergraphs. Electronic Journal of Combinatorics, 25 (3). Art. No. P3.34. ISSN 1077-8926.

[img] PDF - Published Version
Creative Commons Attribution No Derivatives.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemArticle
Conlon, David0000-0001-5899-1829
Additional Information:© 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.
Funding AgencyGrant Number
European Research Council (ERC)676632
Fondo Nacional de Desarrollo Científico y Tecnológico (FONDECYT)11150913
Millenium Nucleus Information and Coordination in NetworksUNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)PE 2299/1-1
European Research Council (ERC)724903
Subject Keywords:Hypergraphs; quasirandom
Issue or Number:3
Record Number:CaltechAUTHORS:20190821-110928639
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98078
Deposited By: Melissa Ray
Deposited On:21 Aug 2019 20:05
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page