Planarity and genus of sparse random bipartite graphs

DOI10.1137/20M1341817zbMATH Open1492.05032arXiv2005.03920OpenAlexW3023190968MaRDI QIDQ5084098FDOQ5084098

Authors: Joshua Erde, Mihyun Kang 

Publication date: 23 June 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: 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_1{n}_2{)}^{-frac12}$ 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_1{n}_2{)}^{-frac12}$ 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)$.

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

Recommendations

• The genus of a random bipartite graph
• The evolution of random graphs on surfaces
• On the genus of a random graph
• Component behaviour and excess of random bipartite graphs near the critical point
• The Evolution of Random Graphs on Surfaces

zbMATH Keywords

cyclesgenusrandom graphscomponentsfacesrandom bipartite graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Cites Work

• Title not available (Why is that?)
• Random Graphs
• Title not available (Why is that?)
• Applications of a Planar Separator Theorem
• Random graphs.
• Title not available (Why is that?)
• Topological graph theory.
• Introduction to Random Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The genus of a random graph
• On the genus of a random graph
• The genus of the Erdős-Rényi random graph and the fragile genus property
• The genus of a random bipartite graph
• The genus of complete 3-uniform hypergraphs
• Some topological methods in graph coloring theory

Cited In (5)

• On the tree-depth and tree-width in heterogeneous random graphs
• The genus of the Erdős-Rényi random graph and the fragile genus property
• The genus of a random bipartite graph
• On the genus of a random graph
• Component behaviour and excess of random bipartite graphs near the critical point

This page was built for publication: Planarity and genus of sparse random bipartite graphs

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