SCIENCE@home

Random graphs embeddable in order‐dependent surfaces

C. McDiarmid,Sophia Saller

Published 2021 in Random Struct. Algorithms

ABSTRACT

Given a ‘genus function’ g=g(n)$$ g=g(n) $$ , we let Eg$$ {\mathcal{E}}^g $$ be the class of all graphs G$$ G $$ such that if G$$ G $$ has order n$$ n $$ (i.e., has n$$ n $$ vertices) then it is embeddable in a surface of Euler genus at most g(n)$$ g(n) $$ . Let the random graph Rn$$ {R}_n $$ be sampled uniformly from the graphs in Eg$$ {\mathcal{E}}^g $$ on vertex set [n]={1,…,n}$$ \left[n\right]=\left\{1,\dots, n\right\} $$ . Observe that if g(n)$$ g(n) $$ is 0 then Rn$$ {R}_n $$ is a random planar graph, and if g(n)$$ g(n) $$ is sufficiently large then Rn$$ {R}_n $$ is a binomial random graph G(n,12)$$ G\left(n,\frac{1}{2}\right) $$ . We investigate typical properties of Rn$$ {R}_n $$ . We find that for every genus function g$$ g $$ , with high probability at most one component of Rn$$ {R}_n $$ is non‐planar. In contrast, we find a transition for example for connectivity: if g(n)$$ g(n) $$ is O(n/logn)$$ O\left(n/\log n\right) $$ and g$$ g $$ is non‐decreasing then lim infn→∞ℙ(Rnis connected)<1$$ \lim\ {\operatorname{inf}}_{n\to \infty}\mathbb{P}\left({R}_n\kern0.3em \mathrm{is}\ \mathrm{connected}\right)<1 $$ , and if g(n)≫n$$ g(n)\gg n $$ then with high probability Rn$$ {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 Eg$$ {\mathcal{E}}^g $$ , and briefly consider corresponding results for unlabelled graphs.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-55 of 55 references · Page 1 of 1

CITED BY