Hypergraphs, quasi-randomness, and conditions for regularity
type: Item
instance of: scholarly article
title: Hypergraphs, quasi-randomness, and conditions for regularity
zbMATH Open document ID: 0990.05111
author: Yoshiharu Kohayakawa
author: Vojtěch Rödl
author: J. Skokan
published in: Journal of Combinatorial Theory. Series A
publication date: 2002-07-04T00:00:00Z
review text: The study of quasi-randomness is a flourishing topic on uniform hypergraphs. F. R. K. Chung and R. L. Graham (among others) investigated thoroughly quasi-random uniform hypergraphs of density 1/2, showing a series of important equivalent statements about these structures. In this investigations the notion of deviation plays a central role. Chung and Graham explicitly asked to extend these investigations to the case where the fixed density differs from 1/2. This extensive paper starts this investigation. Its main aim is to show a series of relevant equivalent statements about quasi-random uniform hypergraphs of fixed (but not 1/2) density. The authors developed a new technique based on the notion of discrepancy and their delicate proofs are quite different from the ones used by Chung and Graham.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1763787
zbMATH Keywords: quasi-random
zbMATH Keywords: random-like
zbMATH Keywords: deviation
zbMATH Keywords: discrepancy
zbMATH Keywords: density
zbMATH Keywords: spectrum of subhypergraphs
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
OpenAlex ID: W2059456505
cites work: Q4230372
cites work: The Algorithmic Aspects of the Regularity Lemma
cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
cites work: Quasi‐random classes of hypergraphs
cites work: Quasi-random hypergraphs
cites work: Quasi-Random Set Systems
cites work: Communication Complexity and Quasi Randomness
cites work: On characterizing hypergraph regularity
cites work: Pseudo-random hypergraphs
cites work: On testing the `pseudo-randomness' of a hypergraph
cites work: Cyclotomy and difference families in elementary Abelian groups
DOI: 10.1006/JCTA.2001.3217
Recommended article: Q4633830
Recommended article: Q5371208
Recommended article: Regularity lemmas for hypergraphs and quasi-randomness
Recommended article: Quasirandomness in hypergraphs
Recommended article: Quasi-random hypergraphs revisited
Recommended article: Quasi-random hypergraphs
Recommended article: Quasi‐random classes of hypergraphs
description: scientific article; zbMATH DE number 1763787