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

2022/02/15 by Jesse Campion Loth, Loth, Jesse Campion, Bojan Mohar +1 · 1 citation
Computer Science · Mathematics · #05C10 #05C80 #Cellular Automata and Applications #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2202.07746

openalex publication_date 2022/02/15 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

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 Θ(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 mth harmonic number. This bound is best possible up to a constant factor.

Cited by

• On the Genus Polynomial of Cubic Graphs

Related

• Face distributions of embeddings of complete graphs
• Variation of the local topological structure of graph embeddings
• The evolution of random graphs on surfaces
• Linking number of monotonic cycles in random book embeddings of complete graphs
• Asymptotics of local face distributions and the face distribution of the complete graph