Structure of large random hypergraphs

By R. Darling, James Norris. 2001

75 citations recorded by the source corpus.

The theme of this paper is the derivation of analytic formulae for certain large combinatorial structures. The formulae are obtained via fluid limits of pure jump-type Markov processes, established under simple conditions on the Laplace transforms of their Levy kernels. Furthermore, a related Gaussian approximation allows us to describe the randomness which may persist in the limit when certain parameters take critical values. Our method is quite general, but is applied here to vertex identifiability in random hypergraphs. A vertex v is identifiable in n steps if there is a hyperedge containing v all of whose other vertices are identifiable in fewer steps. We say that a hyperedge is identifiable if every one of its vertices is identifiable. Our analytic formulae describe the asymptotics of the number of identifiable vertices and the number of identifiable hyperedges for a Poisson(\beta) random hypergraph \Lambda on a set V of N vertices, in the limit as N\to \infty. Here \beta is a formal power series with nonnegative coefficients \beta_0,\beta_1,..., and (\Lambda(A))_{A\subseteq V} are independent Poisson random variables such that \Lambda(A), the number of hyperedges on A, has mean N\beta_j/\pmatrixN j whenever |A|=j.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0f6852e01cc8814a49af4f1b9534a4d871566963

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

An almost-bijective proof of an asymptotic property of partitions (2007, methodology): “Finally, we note that Theorem 1 is very similar to Darling and Norris’s work on identifiability in random undirected hypergraphs [13], where the number of hyperedges of length j is Poisson-distributed with mean βj .”
Differential equation approximations for Markov chains (2007, methodology): “We have found the use of explicit estimates effective, for example, when the Markov chain terminates abruptly on leaving some domain [4], or when convergence is needed over a long time interval [23], or for processes having a large number of components with very different scales [14].”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “[239] Richard WR Darling, James R Norris, et al.”