CaltechAUTHORS
  A Caltech Library Service

Quasirandomness in hypergraphs

Aigner-Horev, Elad and Conlon, David and Hàn, Hiệp and Person, Yury and Schacht, Mathias (2017) Quasirandomness in hypergraphs. Electronic Notes in Discrete Mathematics, 61 . pp. 13-19. ISSN 1571-0653. https://resolver.caltech.edu/CaltechAUTHORS:20190812-163000449

[img] PDF - Submitted Version
See Usage Policy.

622Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-163000449

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/j.endm.2017.06.015DOIArticle
https://www.sciencedirect.com/science/article/pii/S1571065317301002PublisherArticle
https://arxiv.org/abs/1711.04750arXivDiscussion Paper
https://www.dmg.tuwien.ac.at/eurocomb2017/Related ItemConference Site
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© 2017 Published by Elsevier B.V. Available online 3 August 2017. 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.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
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; quasirandomness
Record Number:CaltechAUTHORS:20190812-163000449
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-163000449
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97839
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:16 Aug 2019 20:21
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page