1
$\begingroup$

Can anyone help me with this one?

Let there be a torus with a graph embedding (I hope I'm using the right term). By embedding I mean that the surface of the torus is divided in multiple triangular faces whose nodes and sides form the graph.

The torus has a tree-cotree decomposition. The cotree is the sub-graph that contains all the nodes of the initial graph and all the edges that are not in the tree.

Each edge of the cotree forms a unique loop with the branches of the tree. The loops are of three kinds:

  • $\alpha$-loops are the simplest ones: they do not surround the hole or the torus itself
  • $\beta$-loops surround the torus once (maybe more than once?)
  • $\gamma$-loops surround the torus hole once (maybe more than once?)

Torus with three types of loops

Given only the tree-cotree decomposition is there a an algorithm which can tell the type of loop each cotree edge generates?

Can this method be extended for other multiple connected domains (like a double torus)?

If not, which types of mathematics can help me better understand (and possibly solve) this problem? Of course graph theory is essential, but I suspect topology and abstract algebra are also useful. However these are huge part of mathematics and I really have no clue where to start.

$\endgroup$
1
$\begingroup$

We can distinguish $\alpha$-loops from the others by a computation in the 1-dimensional homology group of the torus.

More explicitly: we work in the vector space generated by the edges of the graph. Assign each edge $xy$ a direction arbitrarily, and say that edge $yx$ is the negative of edge $xy$. A cycle $v_1v_2\dots v_kv_1$ corresponds to the element of this vector space given by the sum $$v_1v_2 + v_2v_3 + \dots + v_kv_1.$$ This vector space has a subspace generated by the faces of the graph: for each triangular face $xyz$, we take the element $xy + yz + zx$.

The $\alpha$-loops are precisely the cycles that are elements of this subspace. We can determine whether this is the case by Gaussian elimination.

We cannot distinguish $\beta$-loops from $\gamma$-loops just from the graph structure: there is an isomorphism of the torus that swaps $\beta$-loops with $\gamma$-loops. For that matter, there are also more complicated loops possible that mix the two kinds: they go around the torus hole as a $\gamma$-loop does, and in the process also wind around the torus some number of times. There's no inherent combinatorial difference between these.

However, if I give you two loops, then another Gaussian elimination can tell us whether they're the same kind of loop (including the number of times they wind around the torus). To do this, just take the difference of the two loops, and see if that difference is in the subspace generated by the faces. If it is, then the two loops are the same kind.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your detailed answer. Can you please tell me if the isomorphism that swaps the two loops has a name? Or maybe where can I find its description? $\endgroup$ – Iam Aug 23 '18 at 13:00
  • $\begingroup$ I don't know of a name; but if you think of the torus as the unit square with opposite sides identified, then the isomorphism is just a $90^\circ$ rotation of the square. $\endgroup$ – Misha Lavrov Aug 23 '18 at 14:51
  • $\begingroup$ Ok. Got it. Thank you very much! $\endgroup$ – Iam Aug 24 '18 at 19:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.