Random 2-cell embeddings of multistars

DOI10.1090/PROC/15899MaRDI QIDQ5086920zbMATH OpenOpenAlexFDO

Authors Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, Bojan Mohar, Robert Šámal

Publication date 8 July 2022

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

dipolegenus distributionmultistarrandom maps

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Random 2-cell embeddings of a given graph $G$ are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, $mathbbE[F_G]$, of such an embedding which is equivalent to studying its average genus. So far, tight results are known for two families called monopoles and dipoles. We extend the dipole result to a more general family called multistars, i.e., loopless multigraphs in which there is a vertex incident with all the edges. In particular, we show that the expected number of faces of every multistar with $n$ nonleaf edges lies in an interval of length $2/(n+1)$ centered at the expected number of faces of an $n$-edge dipole. This allows us to derive bounds on $mathbbE[F_G]$ for any given graph $G$ in terms of vertex degrees. We conjecture that $mathbbE[F_G]leO(n)$ for any simple $n$-vertex graph $G$.

Recommendations

• Topological embeddings into random 2‐complexes
• Enumerating 2-Cell Imbeddings of Connected Graphs
• Approximating codimension two embeddings of cells
• scientific article; zbMATH DE number 3955931
• On Two-Point Configurations in a Random Set
• Random cell complexes and generalised sets
• Random Voronoi cells of higher dimensions
• scientific article; zbMATH DE number 17031
• The asphericity of random 2‐dimensional complexes
• On star decompositions of random regular graphs

Cites work

• A Hypergeometric Analysis of the Genus Series for a Class of 2-Cell Embeddings in Orientable Surfaces
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• An Introduction to Random Topological Graph Theory
• An upper bound for the average number of regions
• Annular embeddings of permutations for arbitrary genus
• Combinatorially refine a Zagier-Stanley result on products of permutations
• Counting Cycles in Permutations by Group Characters, With an Application to a Topological Problem
• Genus distributions for bouquets of circles
• Graphs on surfaces
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• scientific article; zbMATH DE number 474668 (Why is no real title available?)
• scientific article; zbMATH DE number 848096 (Why is no real title available?)
• scientific article; zbMATH DE number 919921 (Why is no real title available?)
• scientific article; zbMATH DE number 3422404 (Why is no real title available?)
• Odd permutations are nicer than even ones
• On an Integral Representation for the Genus Series for 2-Cell Embeddings
• On the average genus of the random graph
• Permutation-partition pairs. III: Embedding distributions of linear families of graphs
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations
• Region distributions of graph embeddings and Stirling numbers
• Sparsity. Graphs, structures, and algorithms
• The Euler characteristic of the moduli space of curves
• Two enumerative results on cycles of permutations
• Valence-partitioned genus polynomials and their application to generalized dipoles

Cited in

(5)

• New bounds for the average genus and average number of faces of a simple graph
• Expected number of faces in a random embedding of any graph is at most linear
• Asymptotics of local face distributions and the face distribution of the complete graph
• Pre-signed graphs: a reformulation of signed graphs and their embeddings
• On the average number of cycles in conjugacy class products

This page was built for publication: Random 2-cell embeddings of multistars

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