On hypergraphs having evenly distributed subhypergraphs
type: Item
instance of: scholarly article
title: On hypergraphs having evenly distributed subhypergraphs
zbMATH Open document ID: 0785.05070
DOI: 10.1016/0012-365X(93)90148-M
published in: Discrete Mathematics
publication date: 1994-04-13T00:00:00Z
review text: A family of \(k\)-uniform hypergraphs of order \(n\) has property \(U(r)\) for \(r\) fixed if every \(k\)-uniform hypergraph of order \(r\) occurs as an induced subgraph about \(n^ r/2^{{r\choose k}}\) times asymptotically as \(n\to \infty\). It was known that \(U(2k)\) implies \(U(r)\) for all fixed \(r\). Now the authors have shown that this is best possible by constructing for each \(s\), \(1\leq s\leq 2k-1\), families for which \(U(s)\) does not imply \(U(s+1)\). Thus, the remarkable phenomenon that occurs for graphs \((k=2)\) also manifests itself for hypergraphs. There are a couple of misprints in the definition. Interchange \(E\) and \(E'\) on line 7, and in equation (1), the binomial coefficient should be \(r\) above \(k\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 428306
zbMATH Keywords: hypergraphs
author: Fan Chung
author: Ron Graham
reviewed by: Edgar M. Palmer
MaRDI profile type: Publication
cites work: Q4099676
cites work: Quasi-random hypergraphs
cites work: Quasi-Random Set Systems
cites work: Quasi-random graphs
cites work: Intersection theorems and mod \(p\) rank of inclusion matrices
cites work: A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
full work available at URL: 0012-365x(93)90148-m
OpenAlex ID: W2120066781
Recommended article: Q4821267
Recommended article: On substructure densities of hypergraphs
Recommended article: Q5588434
Recommended article: Q4316717
Recommended article: Nearly uniform distribution of edges amongk-subgraphs of a graph
Recommended article: Subgraphs in non-uniform random hypergraphs
Recommended article: Equicovering subgraphs of graphs and hypergraphs
Recommended article: The distributions of the numbers of finite subgraphs in random nonhomogeneous hypergraphs
Recommended article: On even-degree subgraphs of linear hypergraphs
Recommended article: On even-cycle-free subgraphs of the hypercube
description: scientific article; zbMATH DE number 428306