Component structure in the evolution of random hypergraphs
type: Item
instance of: scholarly article
title: Component structure in the evolution of random hypergraphs
zbMATH Open document ID: 0573.05042
DOI: 10.1007/BF02579445
author: Jeanette Schmidt-Pruzan
author: Eli Shamir
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: The authors generalize studies of Paul Erdős and A. Rényi on probable structure of random graphs with n labeled vertices and given density. They prove some theorems on the size \(C(d^*(n))\) of the greatest connected component in a random hypergraph. If the hypergraph has n vertices, the size of its largest edge is t, (2\(\leq t\leq 0(\ell n n))\) and the average vertex degree is \(d^*(n)\), then with probability tending to 1 when n tends to infinity: \(C(d^*(n))=0(t\quad \log n)\) for \(d<1\); \(C(d^*(n))=0(n^{2/3})\) for \(d\approx 1\); \(C(d^*(n))=0(n/t)\) for \(d>1\). It means here we can also find the well-known ''double jump'' which was described in case of random graphs.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 3914363
zbMATH Keywords: threshold function
zbMATH Keywords: sparse hypergraph
zbMATH Keywords: random hypergraph
zbMATH Keywords: double jump
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: The longest path in a random graph
cites work: Q5615282
cites work: Cliques in random graphs
cites work: Q3286850
cites work: Q5657249
cites work: Q4065548
cites work: Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
cites work: A threshold for perfect matchings in random d-pure hypergraphs
cites work: Random hypergraph coloring algorithms and the weak chromatic number
cites work: Asymptotical Estimations for the Number of Cliques of Uniform Hypergraphs
full work available at URL: https://doi.org/10.1007/bf02579445
OpenAlex ID: W1977759320
description: scientific article; zbMATH DE number 3914363