Publication
Random graphs embeddable in order-dependent surfaces
Colin McDiarmid; Sophia Saller
In: ArXiv e-prints (arxiv), Pages 1-35, ArXiv, 2021.
Abstract
Given a `genus' function g=g(n), we let 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 E^g on vertex set [n]={1,…,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,12). We investigate typical properties of R_n. We find that for 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 lim inf_{n→∞}P(R_n is connected)<1, and if g(n)≫n 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 E^g, and briefly consider corresponding results for unlabelled graphs.