Cycles in random bipartite graphs

MaRDI QIDQ5167491zbMATH OpenFDO

Authors Yilun Shang

Publication date 9 July 2014

Full work available at URL https://arxiv.org/abs/1310.3526

zbMATH Keywords

bipartite graphcyclerandom graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper we study cycles in random bipartite graph $G(n,n,p)$. We prove that if $pgg{n}^{-2/3}$, then $G(n,n,p)$ a.a.s. satisfies the following. Every subgraph $G^{\prime }subsetG(n,n,p)$ with more than $(1+o(1))n^{2}p/2$ edges contains a cycle of length $t$ for all even $tin[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.

Recommendations

• Bipartite Ramsey numbers of cycles for random graphs
• Cycles in random graphs
• Edge condition for a Hamiltonian bipartite graph to be bipancyclic
• On the Hamiltonicity of random bipartite graphs
• Limit distribution for the existence of Hamiltonian cycles in random bipartite graphs

Cited in

(4)

• Bipartite Ramsey numbers of cycles for random graphs
• Multicyclic components in a random graph process
• Cycles and Unicyclic Components in Random Graphs
• Random bipartite Ramsey numbers of long cycles

This page was built for publication: Cycles in random bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167491)