3
$\begingroup$

Take an undirected graph $G$, where every vertex has at least two edges (we count self-loops as two edges). For each vertex $v$, we define a regular deg($v$)-gon. For each edge between $v_1$ and $v_2$, we glue one of the edges of their polygon together (arbitrarily). We never glue an edge to itself.

This will give us a surface (which will be compact if $G$ is finite). How many surfaces will there be, up to homeomorphism (or how do you calculate this number, or establish bounds on it)?

Note that different surfaces can pop up, depending on how you glue things together. For example, a vertex with two self-loops, it can be a torus or a Klein bottle or a projective plane or a sphere.

We have $\Pi_{v\in V(G)}2(\text{deg($v$)}-1)!$ as an upper bound (the factor $2$ is because of orientation).

Improve this question
$\endgroup$
14
  • $\begingroup$ (singular of vertices is vertex, just fyi) $\endgroup$
    – Wojowu
    Commented Jan 23, 2018 at 19:44
  • $\begingroup$ The answer is "1". Or maybe you mean, how many when $G$ varies... under which restriction? $G$ ranges over finite graphs? connected? with some restriction on the number of vertices?... $\endgroup$
    – YCor
    Commented Jan 23, 2018 at 19:44
  • $\begingroup$ @YCor I mean if you connect them in different orders. For example, Imagine that $G$ is a vertex $v$ with four self loops. Then the topology could be a torus, klein bottle, projective plane, or even sphere. $\endgroup$
    – Christopher King
    Commented Jan 23, 2018 at 19:46
  • $\begingroup$ For each vertex, to define a polygon, you need some cyclic ordering of the set of edges at this vertex. So this sounds ill-defined. $\endgroup$
    – YCor
    Commented Jan 23, 2018 at 19:46
  • 1
    $\begingroup$ The number of cyclic orderings at a given vertex $v$ of degree $d$ is much more than $2d$. It's $d!/d=(d-1)!$. $\endgroup$
    – YCor
    Commented Jan 23, 2018 at 19:48

1 Answer 1

Reset to default
4
$\begingroup$

It sounds like you are trying to enumerate ribbon graphs, in which case you might want to look at:

Do, Norman; Manescu, David, Quantum curves for the enumeration of ribbon graphs and hypermaps, Commun. Number Theory Phys. 8, No. 4, 677-701 (2014). ZBL1366.14034.

There is an arxiv.org version: arXiv:1312.6869.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .