1 results
The Genus of a Random Bipartite Graph
- Part of
-
- Journal:
- Canadian Journal of Mathematics / Volume 72 / Issue 6 / December 2020
- Published online by Cambridge University Press:
- 29 August 2019, pp. 1607-1623
- Print publication:
- December 2020
-
- Article
- Export citation
-
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)\geqslant 3(\ln n)^{2}n^{-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}\geqslant n_{2}\gg 1$, phase transitions occur for every positive integer 
$i$ when 
$p=\unicode[STIX]{x1D6E9}((n_{1}n_{2})^{-i/(2i+1)})$. A different behaviour is exhibited when one of the bipartite parts has constant size, i.e., 
$n_{1}\gg 1$ and 
$n_{2}$ is a constant. In that case, phase transitions occur when 
$p=\unicode[STIX]{x1D6E9}(n_{1}^{-1/2})$ and when 
$p=\unicode[STIX]{x1D6E9}(n_{1}^{-1/3})$.
