Người báo cáo: Đỗ Tuấn Anh (Đại học Sư phạm Hà Nội 2)
Thời gian: 14h Thứ 5, ngày 7/10/2021
Link Online:
meet.google.com/nqs-ntdh-wnz
Abstract: In this talk we show that there is a threshold for planarity of the random bipartite graph $G(n_1,n_2,p)$ (a graph on two sets of vertices $N_1$ and $N_2$ whose sizes are $n_1$ and $n_2$ respectively, and each edge connects one vertex in $N_1$ and one in $N_2$ independently with probability p) 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 with high probability the genus is linear in the number of edges, than in the case where $n_1$ is asymptotically smaller than $n_2$, when with high probability the genus behaves like the genus of a sparse random graph $G(n_1,q)$ (a graph on $n_1$ vertices and each edge appears independently with probability $q$) for an appropriately chosen $q=q(p,n_1,n_2)$. This is a joint work with Joshua Erde and Mihyun Kang. |
