Planarity and genus of sparse random bipartite graphs

DOI10.1137/20M1341817MaRDI QIDQ5084098zbMATHOpenAlexFDO

Authors Joshua Erde, Mihyun Kang

Publication date 23 June 2022

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

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

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)

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)$.

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3198646 (Why is no real title available?)
• Applications of a Planar Separator Theorem
• Introduction to Random Graphs
• On the genus of a random graph
• Random Graphs
• Random graphs.
• Some topological methods in graph coloring theory
• The genus of a random bipartite graph
• The genus of a random graph
• The genus of complete 3-uniform hypergraphs
• The genus of the Erdős-Rényi random graph and the fragile genus property
• Topological graph theory.

Cited in

(5)

• On the genus of a random graph
• Component behaviour and excess of random bipartite graphs near the critical point
• 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

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)