Appearance of complex components in a random bigraph

This is an investigation into the limiting distribution of the sparse connected components in an n 1 × n 2 bipartite multigraph with approximately ½ n edges, where n 1 , n 2 ≈ ½ n. We will show that the probability of finding no complex components in a random n 1 × n 2 bigraph, with approximately ½ n edges, is asymptotically the same as for random graphs with n vertices and approximately ½ n edges, namely √2/3. In addition, we will show that, for n 1 × n 2 multi‐bigraphs, the probability distribution for finitely many bicyclic components, tricyclic components, etc., with no components having more than a given number of cycles, asymptotically equals the corresponding distribution for random multigraphs with n vertices and approximately half as many edges. As an application of this analysis we present a method for estimating the efficiency of memory access in a distributed, replicated data base.