Expected number of faces in a random embedding of any graph is at most linear

DOI10.1017/S096354832300010XMaRDI QIDQ6085874zbMATH OpenOpenAlexFDO

Authors Jesse Campion Loth, Bojan Mohar

Publication date 8 November 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

average genusrandom embeddingsrandom topological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: A random 2-cell embedding of a given graph $G$ is obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces of such an embedding, which is equivalent to studying its average genus. In 1991, Stahl proved that the expected number of faces in a random embedding of an arbitrary graph of order $n$ is at most $nlog(n)$. While there are many families of graphs whose expected number of faces is $Theta(n)$, none are known where the expected number would be super-linear. This lead to the conjecture that there is a linear upper bound. In this note we confirm the conjecture by proving that for any $n$-vertex multigraph, the expected number of faces in a random 2-cell embedding is at most $n(1+H_m)$, where $m$ is the maximum edge-multiplicity and $H_m$ denotes the $m$th harmonic number. This bound is best possible up to a constant factor.

Recommendations

• Random 2-cell embeddings of multistars
• On the average genus of the random graph
• The genus of a random graph
• An Introduction to Random Topological Graph Theory
• The Evolution of Random Graphs on Surfaces

Cites work

• An Introduction to Random Topological Graph Theory
• An upper bound for the average number of regions
• Graphs on surfaces
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3422404 (Why is no real title available?)
• On the average genus of the random graph
• Random 2-cell embeddings of multistars
• Two enumerative results on cycles of permutations

Cited in

(2)

• New bounds for the average genus and average number of faces of a simple graph
• Asymptotics of local face distributions and the face distribution of the complete graph

This page was built for publication: Expected number of faces in a random embedding of any graph is at most linear

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