Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnaya Matematika, 1995, Volume 7, Issue 4, Pages 86–94 (Mi dm609)  

The number of components in a random bipartite graph

A. I. Saltykov
Abstract: 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.
Received: 15.11.1994
Bibliographic databases:
UDC: 519.2
Language: Russian
Citation: A. I. Saltykov, “The number of components in a random bipartite graph”, Diskr. Mat., 7:4 (1995), 86–94; Discrete Math. Appl., 5:6 (1995), 515–523
Citation in format AMSBIB
\Bibitem{Sal95}
\by A.~I.~Saltykov
\paper The number of components in a random bipartite graph
\jour Diskr. Mat.
\yr 1995
\vol 7
\issue 4
\pages 86--94
\mathnet{http://mi.mathnet.ru/dm609}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=1376197}
\zmath{https://zbmath.org/?q=an:0847.05085}
\transl
\jour Discrete Math. Appl.
\yr 1995
\vol 5
\issue 6
\pages 515--523
Linking options:
  • https://www.mathnet.ru/eng/dm609
  • https://www.mathnet.ru/eng/dm/v7/i4/p86
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:486
    Full-text PDF :221
    References:2
    First page:2
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025