The number of components in a random bipartite graph

A. I. Saltykov

Diskretnaya Matematika, Tome 7 (1995) no. 4, pp. 86-94.

Résumé

We consider a bipartite graph $G(n_1,n_2,T)$ with $n_1$ vertices in the first part and $n_2$ vertices in the second one. This graph is obtained by $T$ independent trials, each of them consists of drawing an edge which joins two vertices chosen independently of each other from distinct parts. Let $n_1\ge n_2$, $\alpha=n_2/n_1$, $n=n_1+n_2$. We prove that if $n\to\infty$ and $(1+\alpha)T=n\ln n+xn+o(n)$, where $x$ is a fixed number, then, with probability tending to one, the graph $G(n_1,n_2,T)$ contains one giant connected component and isolated vertices whose number is distributed by the Poisson law.