Y Shang. On the hamiltonicity of random bipartite graphs
Natural Sciences / Mathematics / Combinatorics
Submitted on: Mar 08, 2013, 18:49:50
Description: We prove that if $pggln n/n$, then a.a.s. every subgraph of random bipartite graph $G(n,n,p)$ with minimum degree at least $(1/2+o(1))np$ is Hamiltonian. The range of $p$ and the constant $1/2$ involved are both asymptotically best possible. The result can be viewed as a generalization of the Dirac theorem within the context of bipartite graphs. The proof uses P'osa's rotation and extension method and is closely related to a recent work of Lee and Sudakov.