论文标题
稀疏随机两分图的平面性和属
Planarity and genus of sparse random bipartite graphs
论文作者
论文摘要
二项式随机图$ g（n，p）$的属在$ p = p（n）$的广泛范围内得到很好的理解。最近，Mohar and Ying对随机两分图$ G（N_1，N_2，P）$的研究进行了研究，分区尺寸$ n_1 $和$ n_2 $发起了，他们表明，当$ N_1 $和$ n_2 $相比，$ N_1 $和$ n_2是可比较的，而$ P = P = P = n_1，N_1，N_1，N_1，N_1，N_1，N_1，N_1，N_1，N_2 $。 $（n_1n_2）^{ - \ frac {1} {2}} $随机二分图的属具有与二项式随机图相似的行为。 在本文中，我们表明，在$ p =（n_1n_2）^{ - \ frac {1} {2}} $平面上有一个随机两分图的阈值，并研究了接近此阈值的属，扩展了Mohar和ying的结果。事实证明，在$ n_1 $和$ n_2 $的情况下，有质量不同$ q = q（p，n_1，n_2）$。
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)$.
