The phase transition in a random hypergraph
type: Item
instance of: scholarly article
title: The phase transition in a random hypergraph
zbMATH Open document ID: 0995.05131
DOI: 10.1016/S0377-0427(01)00464-2
author: Michal Karonski
author: Tomasz Łuczak
published in: Journal of Computational and Applied Mathematics
publication date: 2002-08-22T00:00:00Z
review text: A \(d\)-uniform hypergraph \(H\) consists of a set \(V\) of \(n\) vertices and a family \({\mathcal E}\) of \(d\)-element subsets of \(V\) called edges. (Thus a graph is a 2-uniform hypergraph.) Two vertices \(u,v\in V\) are connected if there is a sequence of vertices \(v_{1},\dots v_{r-1}\) and edges \(e_{1},\dots e_{r}\) such that (writing \(u=v_{0}\) and \(v=v_{r}\) for convenience) we have \(\{v_{i},v_{i+1}\} \subseteq e_{i+1}\) for all \(0\leq i\leq (r-1)\). A set \(S\) of vertices is connected if every pair of vertices in \(S\) is connected. A component is a maximal connected subset of \(\{1,2\dots, n\}\): the order of a component is the number of vertices in it. The number of connected \(d\)-uniform hypergraphs with \(r=s(d-1)-k\) vertices and \(s\) edges will be denoted \(C_{d}(s,k)\). We say \(H\) is a tree if (in the same notation) \(k=s(d-1)-r\) is \(-1\), and that it is unicyclic if \(k=0\). (In all asymptotic estimates which follow, \(d\) should be regarded as fixed: thus implied constants are likely to depend on \(d\).) A random hypergraph \({\mathbb{G}}^{d}(n,M(n))\) is a hypergraph chosen uniformly and at random from the \(d\)-uniform labelled hypergraphs on vertex set \(\{1,2,\dots n\}\) and \(M(n)\) edges. We say that a random hypergraph has a certain property \(\wp\) a.a.s if \[ \lim_{n\rightarrow\infty}P\left( {\mathbb{G}}^{d}(n,M(n))\text{ has }\wp\right)=1. \] In the case \(d=2\), i.e. random graphs, a number of by now standard results, summarised in Chapter 6 of \textit{S. Janson, T. Łuczak and A. Ruciński} [Random graphs (Wiley, New York) (2000; Zbl 0968.05003)] show that if \(M(n)=cn\) then for \(c<1/2\) a.a.s. all components are trees or unicyclic, and their order is \(\log(n)\), but for \(c>1/2\) a.a.s one `giant'component, whose order is linear in \(n\), emerges. The situation for \(c\sim 1/2\) is more delicate. Let, for the rest of this review, \(m=m(n)\) be a function of \(n\) such that \(\lim_{n\to\infty} m/n^{2/3}=\infty\) but \(m=o(…
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1787601
zbMATH Keywords: random hypergraph
zbMATH Keywords: phase transition
zbMATH Keywords: largest component
reviewed by: David B. Penman
MaRDI profile type: Publication
cites work: The asymptotic number of labeled connected graphs with a given number of vertices and edges
cites work: The Evolution of Random Graphs
cites work: Q3682518
cites work: Q3286850
cites work: The birth of the giant component
cites work: Q4519896
cites work: The number of connected sparsely edged uniform hypergraphs
cites work: Component behavior near the critical point of the random graph process
cites work: Component structure in the evolution of random hypergraphs
description: scientific article; zbMATH DE number 1787601