Premium
Appearance of complex components in a random bigraph
Author(s) -
Delaurentis J.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070405
Subject(s) - multigraph , combinatorics , mathematics , bipartite graph , random graph , distribution (mathematics) , discrete mathematics , graph , mathematical analysis
Abstract 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.