DIKUL - logo
FMF, Mathematical Library, Lj. (MAKLJ)
  • The genus of a random bipartite graph
    Jing, Yifan ; Mohar, Bojan, 1956-
    Archdeacon and Grable (1995) proved that the genus of the random graph ▫$G\in\mathcal{G}_{n,p}$▫ is almost surely close to ▫$pn^2/12$▫ if ▫$p=p(n)\geq3(\ln n)^2n^{-1/2}$▫. In this paper we prove an ... analogous result for random bipartite graphs in ▫$\mathcal{G}_{n_1,n_2,p}$▫. If ▫$n_1\ge n_2 \gg 1$▫, phase transitions occur for every positive integer ▫$i$▫ when ▫$p=\Theta((n_1n_2)^{-i/(2i+1)})$▫. A different behaviour is exhibited when one of the bipartite parts has constant size, ▫$n_1\gg1$▫ and ▫$n_2$▫ is a constant. In that case, phase transitions occur when ▫$p=\Theta(n_1^{-1/2})$▫ and when ▫$p=\Theta(n_1^{-1/3})$▫.
    Source: Canadian journal of mathematics = Journal canadien de mathématiques. - ISSN 0008-414X (Vol. 72, no. 6, Dec. 2020, str. 1607-1623)
    Type of material - article, component part ; adult, serious
    Publish date - 2020
    Language - english
    COBISS.SI-ID - 58643459

    Link(s):

    https://doi.org/10.4153/S0008414X19000440
    DOI

Shelf entry