Structure of large random hypergraphs

• 成果类型: Article
• 署名作者: Darling, RWR; Norris, JR
• 署名单位: University of Cambridge
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051604000000567
• 发表日期: 2005
• 页码: 125-152
• 关键词: differential-equations

摘要

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 A on a set V of N vertices, in the limit as N --> infinity. Here is a formal power series with nonnegative coefficients beta(0), beta(1), ..., and (Lambda(A))(Asubset of or equal toV) are independent Poisson random variables such that A(A), the number of hyperedges on A, has mean Nbetaj/((N)(j)) whenever \A\ = j.