Structure of large random hypergraphs
type: Item
instance of: scholarly article
title: Structure of large random hypergraphs
zbMATH Open document ID: 1062.05132
DOI: 10.1214/105051604000000567
published in: The Annals of Applied Probability
publication date: 2005-04-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/0503460
review text: This paper studies random hypergraphs. Here a hypergraph consists of a vertex set \(V\) of \(N\) vertices and a function \(\Lambda : {\mathcal P}(V)\rightarrow {\mathbb N}\cup \{0\}\) (the image of a subset \(A\) being thought of as the multiplicity of \(A\) as a hyperedge: so the objects are really multi-hypergraphs). Hyperedges over vertices (i.e. 1-element subsets) are called patches: a hypergraph with no patches is said to be stable. Now let \((X,\text{Im},P)\) be a probability space and say that a random hypergraph on \(V\) is a measurable map \(\Lambda: \Omega\times {\mathcal P}(V)\rightarrow {\mathbb N}\cup \{0\}\). Thus the result of the experiment in \(\Omega\) and the function \(\Lambda\) determine the multiplicity of each subset as a hyperedge, and we can talk about the random variable \(\Lambda(A)\) for \(A\in {\mathcal P}(V)\). The main results are for Poisson(\(\beta\)) random hypergraphs, for a sequence \(\beta=(\beta_{j})\) of nonnegative numbers. Here \(\Lambda\) has the additional features that (1) the random variables \(\Lambda(A)\), as \(A\) ranges over subsets of \(V\), are independent, (2) the distribution of \(\Lambda(A)\) depends only on \(| A|\), and (3) \(\sum_{| A|=j}\Lambda(A)\sim \text{ Po}(N\beta_{j})\): here \(X\sim \text{ Po}(\lambda)\) means \(X\) has a Poisson distribution with parameter \(\lambda\). Crudely speaking, a \(\text{ Po}(N\beta_{k})\) number of hyperedges is scattered randomly over all subsets of size \(k\). We need one more definition before stating some results. Let \(\beta(t)=\sum_{j=0}^{\infty}\beta_{j}t^{j}\) have radius of convergence \(R\). Set \[ \begin{aligned} z^{*}&=\inf\{t\in [0,1):\,\beta '(t)+\log(1-t)<0\}\wedge 1\\ \text{and} \zeta&= \{t\in [0,z^{*}):\,\beta '(t)+\log(1-t)=0\}. \end{aligned} \] The simplest, and also the generic, case is \(\zeta=\emptyset\). The authors first study a generalisation of the connectivity of graphs to the hypergraph context. We say a vertex \(v\in V\) is identifiable in one st…
reviewed by: David B. Penman
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 60J75
zbMATH DE Number: 2162823
zbMATH Keywords: jump process
zbMATH Keywords: collapsing
zbMATH Keywords: identifiability
author: Richard W. R. Darling
author: James R. Norris
MaRDI profile type: Publication
OpenAlex ID: W3105201570
arXiv ID: math/0503460
cites work: Lower bounds for random 3-SAT via differential equations
cites work: Rigorous results for random (\(2+p)\)-SAT
cites work: Q3682518
cites work: Q4471319
cites work: Continuous and discontinuous phase transitions in hypergraph processes
cites work: Q4871755
cites work: Q3286850
cites work: Q3721531
cites work: Q3774629
cites work: Foundations of Modern Probability
cites work: Q4878665
cites work: Q4726286
cites work: Cluster coagulation
cites work: Component structure in the evolution of random hypergraphs
cites work: On the critical exponents of random k‐SAT
cites work: Differential equations for random processes and random graphs
description: scientific article