Article ID Journal Published Year Pages File Type
4664629 Acta Mathematica Scientia 2011 12 Pages PDF
Abstract

In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows: let m = m(n) be a positive integer-valued function on n   and GG(n, m; {pk}) the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A = {a1, a2, … an} and B = {b1, b2 … bm}, in which the numbers tai,bjtai,bj of the edges between any two vertices ai ∈ A and bj ∈ B are identically distributed independent random variables with distributionP{tai,bj = k} = pk, k = 0, 1, 2, ⋯,P{tai,bj = k} = pk, k = 0, 1, 2, ⋯,where pk ≥ 0 and ∑pk = 1k=0∞. They obtain that Xc,d,A, the number of vertices in A with degree between c and d of Gn, m ∈ GG (n, m;{pk}) has asymptotically Poisson distribution, and answer the following two questions about the space GG(n, m;{pk}) with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D(n) such that almost every random multigraph Gn, m ∈ GG (n, m;{pk}) has maximum degree D(n) in A? under which condition for {pk} has almost every multigraph Gn, m ∈ GG (n, m;{pk}) a unique vertex of maximum degree in A?

Related Topics
Physical Sciences and Engineering Mathematics Mathematics (General)
Authors
, , ,