Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 24, 2018 | Published
Journal Article Open

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.

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.

Attached Files

Published - EJC25.3.34.pdf

Files

EJC25.3.34.pdf
Files (561.3 kB)
Name Size Download all
md5:fe0b310373b9cf2504a46c481e5d1b04
561.3 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 18, 2023