THE MAXIMUM AND MINIMUM DEGREES OF RANDOM BIPARTITE MULTIGRAPHS

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 g(n, m; {p(k)}) the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A = {a(1), a(2), ..., a(n)} and B = {b(1), b(2), ..., b(m)}, in which the numbers of the edges between any two vertices a(i) is an element of A and b(j) is an element of B are identically distributed independent random variables with distribution P{ta(i), b(j) = k} = p(k), k = 0, 1, 2, ..., where p(k) >= 0 and Sigma(infinity)(k=0) p(k) =1. They obtain that X(c,d,A,) the number of vertices in A with degree between c and d of G(n, m) is an element of g(n, m; {p(k)}) has asymptotically Poisson distribution, and answer the following two questions about the space g(n,m; {p(k)}) with {p(k)} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {p(k)} can there be a function D(n) such that almost every random multigraph G(n,m) is an element of g(n, m; {p(k)}) has maximum degree D(n) in A? under which condition for {p(k)} has almost every multigraph G(n,m) is an element of g(n, m; {p(k)}) a unique vertex of maximum degree in A?