Structure of large random hypergraphs

Details Structure of large random hypergraphs Structure of large random hypergraphs

2005-03-22

arxiv.org/abs/math/0503460v1

Annals of Applied Probability 2005, Vol. 15, No. 1A, 125-152

Mathematics

Probability

Published at http://dx.doi.org/10.1214/105051604000000567 in the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051604000000567

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.

Affiliated with

Also associated with

No associations

Rating

Structure of large random hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Structure of large random hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structure of large random hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684550