Cycles in Random Bipartite Graphs

Abstract

In this paper we study cycles in random bipartite graph $G(n,n,p)$. We prove that if $p\gg n^{-2/3}$, then $G(n,n,p)$ a.a.s. satisfies the following. Every subgraph $G^{\prime }\subset G(n,n,p)$ with more than $(1+o(1))n^{2}p/2$ edges contains a cycle of length $t$ for all even $t\in [4,(1+o(1))n/30]$. Our theorem complements a previous result on bipancyclicity, and is closely related to a recent work of Lee and Samotij.

8 pages, 2 figures

References in corpus (1)

• Bipancyclic subgraphs in random bipartite graphs