Cyclization in bipartite random graphs.

In this paper the time evolution of a finite bipartite graph initially comprising two sorts of isolated vertices is considered. The graph is assumed to evolve by adding edges, one at a time. Each new edge connects either two linked components and forms a new component of a larger order (coalescence of graphs) or increases (by one) the number of edges in a given linked component (cycling). Any state of the graph is thus characterized by the set of occupation numbers (the numbers of linked components comprising a given numbers of vertexes of the both sorts and a given number of edges. Once the rate of appearance of an extra edge in the graph being known, the master equation governing the time evolution of the probability to find the random graph in a given state is reformulated in terms of the functional generating the probability to find the evolving graph in a given state. The exact solution of the evolution equation for the generating functional applies for analyzing the average population numbers of linked components. In the limit of large order of the graph the distribution factorizes into two multipliers, one of which is just the spectrum of linked components in the infinite bipartite graph, The second multiplier includes the dependence on the total size of the graph. Both these multipliers contain information on the emergence of the giant component that forms at a critical time.