2021/08/17 by McDiarmid, Colin, Saller, Sophia · 1 citation
#05C10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.07666
Given a `genus' function g=g(n), we let Eg 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 Rn be sampled uniformly from the graphs in Eg on vertex set [n]=\1,…,n\. Observe that if g(n) is 0 then Rn is a random planar graph, and if g(n) is sufficiently large then Rn is a binomial random graph G(n,\tfrac12). We investigate typical properties of Rn. We find that for every genus function g, with high probability at most one component of Rn is non-planar. In contrast, we find a transition for example for connectivity: if g is non-decreasing and g(n) = O(n/log n) then \liminfn → ∞ ℙ(Rn is connected) < 1, and if g(n) ≫ n then with high probability Rn 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 Eg, and briefly consider corresponding results for unlabelled graphs.