7
$\begingroup$

Here is a combinatorial problem which is hard to Google but seems like it might have a solution well known to people who study finite type invariants etc.

Let $G_{g,b}$ denote the set of finite undirected connected graphs with exactly $2g-2+b \geq 0$ trivalent vertices, $b \geq 0$ vertices of valence $1$, and no vertices of any other valence. We consider the trivalent vertices as indistinguishable, but the 1-valent vertices are ordered. Let $G_{g,b}'$ denote the subset consisting of graphs without loops (=edges which start and end at the same vertex).

We need the notion of an IH-move. We say that two graphs in $G_{g,b}$ are related via an IH-move if one can be obtained from the other by first collapsing an edge connecting two trivalent vertices, and then "uncollapsing" it in a different way. See e.g. Figure 1 here.

We build a 1-dimensional CW complex with vertex set $G_{g,b}$ and an edge connecting two graphs for every IH-move taking one to the other. This complex is connected. Question: is there a description of the 2-cells that one needs to glue in to make it simply connected?

In fact I'd be more interested in the analogue for $G_{g,b}'$. In this case we need to impose the condition that we apply an IH-move only to an edge which is not parallel with any other edge, as in that case we create a loop in the graph.

Remark. If instead of regular old graphs we had ribbon graphs, i.e. graphs with a cyclic ordering of incoming edges at each vertex, then we would be describing what Penner calls the Ptolemy groupoid. In this case there is a known set of 2-cells one needs to glue in, namely that doing the same IH-move twice gives the identity, that disjoint IH-moves commute, and a certain "pentagon relation".

$\endgroup$
  • $\begingroup$ It turned out to be not so difficult. You need the same moves as in the Ptolemy groupoid and a three-term relation encoding that since the graphs aren't ribbon, there are two IH-moves you can do at any given edge, and those two are in turn related via an IH-move. $\endgroup$ – Dan Petersen Sep 9 '18 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.