Structure of large random hypergraphs (Q1774214): Difference between revisions

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 step if \(\Lambda(\{v\})\geq 1\). It is identifiable in \(n\) steps if it is in some subset \(A\), with \(\Lambda(A)\geq 1\), all other vertices of \(A\) being identifiable in strictly less than \(n\) steps, and is identifiable if it is identifiable in \(n\) steps for some \(n\geq 1\). Think of the identification as a process over time: once a vertex is identified, we replace the current hypergraph \(\Lambda\) by a new one \(\Lambda'\) by removing \(v\) from the vertex set and also from any hyperedge of which it is a member. This is a collapsing process: we say that a collapse is permitted if \(\Lambda(\{v\})\geq 1\). Starting from any finite \(\Lambda\) we obtain in a finite number of permitted collapses a stable hypergraph \(\Lambda_{\infty}\) (independent of the order in which collapses are carried out). The identifiable vertices, \(V^{*}\) are precisely the vertices removed in the collapsing process. We let \(\Lambda^{*}\) be the identifiable hypergraph: this is defined by the rule \[ \Lambda^{*}(A)=\Lambda(A) I_{A\subseteq V^{*}} \] where \(I\) is an indicator function. Thus \(| \Lambda^{*}|\) is the number of identifiable hyperedges. The main result is a limiting theorem, as \(N\rightarrow\infty\), for \(V^{*}\) and \(\Lambda^{*}\) when \(\Lambda^{N}\) is a Poisson(\(\beta\)) random hypergraph on \(N\) vertices, the limits being convergence in probability. It is stated first in the `generic'\, case \(z^{*}<1\) and \(\zeta=\emptyset\): here \[ | V^{N*}|/N\rightarrow z^{*}\quad \text{and}\quad | \Lambda^{N*}|/N\rightarrow \beta(z^{*})-(1-z^{*})\log(1-z^{*}). \] The extension to the case where \(\zeta\neq \emptyset\) requires a standard Brownian motion \((W(t))\) for all \(t\geq 0\). Define a random variable \(Z\) by \[ Z=\min\{z\in \zeta:\,W(z/(1-z))<0\}\wedge z^{*}. \] Then, without the assumption \(z^{*}<1\) and \(\zeta=\emptyset\), but assuming that \(R\) (the radius of convergence of \(\beta(t)\)) is not in \(\zeta\), we have \[ | V^{N*}|/N\rightarrow Z\quad \text{and}\quad | \Lambda^{N*}|/N\rightarrow \beta(Z)-(1-Z)\log(1-Z). \] Here is some idea of the proofs. First, in Section 3, a certain random rule for choosing the sequence of moves by which the hypergraph is collapsed, which has the advantage that certain key statistics of the evolving hypergraph become Markov chains, is introduced. By using (essentially standard) results about exponential martingales associated with pure jump Markov processes in \({\mathbb R}^{d}\) (recalled in Section 4), criteria for the convergence of a sequence of Markov chains in \({\mathbb R}^{d}\) to the solution of a differential equation are given: this is similar in spirit to the `differential equations method\'\, of N.C. Wormald and co-workers, though differing in detail. (Readers may find the `user's guide\'\, to the technology at http://front.math.ucdavis.edu/math.PR/0210109 useful.) This theory then yields the main results. The various passages between discrete and continuous time will be interesting for those approaching the paper from the combinatorial (and hence `discrete-time\') perspective: it seems likely similar ideas may eventually be useful in other such contexts. See http://front.math.ucdavis.edu/math.PR/0401143, http://front.math.ucdavis.edu/math.PR/0312451 or http://front.math.ucdavis.edu/math.PR/0109020 for some ongoing work on topics close to the paper.