Charles Explorer logo
🇨🇿

RANDOM 2-CELL EMBEDDINGS OF MULTISTARS

Publikace na Matematicko-fyzikální fakulta |
2022

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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, E[FG], 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 E[FG] for any given graph G in terms of vertex degrees.

We conjecture that E[FG] <=O(n) for any simple n-vertex graph G.