Random graphs embeddable in order-dependent surfaces

DOI10.1002/RSA.21199arXiv2108.07666MaRDI QIDQ6375437FDOQ6375437

Authors: Colin McDiarmid, Sophia Saller 

Publication date: 17 August 2021

Abstract: Given a `genus' function $g=g(n)$, we let $mathcal{E}^g$ be the class of all graphs $G$ such that if $G$ has order $n$ (that is, has $n$ vertices) then it is embeddable in a surface of Euler genus at most $g(n)$. Let the random graph $R_n$ be sampled uniformly from the graphs in $mathcal{E}^g$ on vertex set $[n]=1,ldots,n$. Observe that if $g(n)$ is 0 then $R_n$ is a random planar graph, and if $g(n)$ is sufficiently large then $R_n$ is a binomial random graph $G(n,frac12)$. We investigate typical properties of $R_n$. We find that for emph{every} genus function $g$, with high probability at most one component of $R_n$ is non-planar. In contrast, we find a transition for example for connectivity: if $g$ is non-decreasing and $g(n)=O(n/logn)$ then $limin{f}_{noinfty}mathbbP(R_{n}mboxisconnected)<1$, and if $g(n)ggn$ then with high probability $R_n$ is connected. These results also hold when we consider orientable and non-orientable surfaces separately. We also investigate random graphs sampled uniformly from the `hereditary part' or the `minor-closed' part of $mathcal{E}^g$, and briefly consider corresponding results for unlabelled graphs.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

This page was built for publication: Random graphs embeddable in order-dependent surfaces

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