Name
Abstract | ||
|---|---|---|
The genus of the binomial random graph $G(n,p)$ is well understood for a wide range of $p=p(n)$. Recently, the study of the genus of the random bipartite graph $G(n_1,n_2,p)$, with partition classes of size $n_1$ and $n_2$, was initiated by Mohar and Ying, who showed that when $n_1$ and $n_2$ are comparable in size and $p=p(n_1,n_2)$ is significantly larger than $(n_1n_2)^{-\frac{1}{2}}$ the genus of the random bipartite graph has a similar behaviour to that of the binomial random graph. In this paper we show that there is a threshold for planarity of the random bipartite graph at $p=(n_1n_2)^{-\frac{1}{2}}$ and investigate the genus close to this threshold, extending the results of Mohar and Ying. It turns out that there is qualitatively different behaviour in the case where $n_1$ and $n_2$ are comparable, when whp the genus is linear in the number of edges, than in the case where $n_1$ is asymptotically smaller than $n_2$, when whp the genus behaves like the genus of a sparse random graph $G(n_1,q)$ for an appropriately chosen $q=q(p,n_1,n_2)$. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/20M1341817 | SIAM Journal on Discrete Mathematics |
DocType | Volume | Citations |
Journal | 36 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Do Tuan Anh | 1 | 0 | 0.34 |
| Erde Joshua | 2 | 0 | 0.34 |
| Mihyun Kang | 3 | 163 | 29.18 |