Ribbon Graphs¶
This file implements objects called ribbon graphs. These are graphs together with a cyclic ordering of the darts adjacent to each vertex. This data allows us to unambiguously “thicken” the ribbon graph to an orientable surface with boundary. Also, every orientable surface with non-empty boundary is the thickening of a ribbon graph.
AUTHORS:
- Pablo Portilla (2016)
-
sage.geometry.ribbon_graph.
RibbonGraph
¶ A ribbon graph codified as two elements of a certain permutation group.
A comprehensive introduction on the topic can be found in the beginning of [GGD2011] Chapter 4. More concretely, we will use a variation of what is called in the reference “The permutation representation pair of a dessin”. Note that in that book, ribbon graphs are called “dessins d’enfant”. For the sake on completeness we reproduce an adapted version of that introduction here.
Brief introduction
Let \(\Sigma\) be an orientable surface with non-empty boundary and let \(\Gamma\) be the topological realization of a graph that is embedded in \(\Sigma\) in such a way that the graph is a strong deformation retract of the surface.
Let \(v(\Gamma)\) be the set of vertices of \(\Gamma\), suppose that these are white vertices. Now we mark black vertices in an interior point of each edge. In this way we get a bipartite graph where all the black vertices have valency 2 and there is no restriction on the valency of the white vertices. We call the edges of this new graph darts (sometimes they are also called half edges of the original graph). Observe that each edge of the original graph is formed by two darts.
Given a white vertex \(v \in v(\Gamma)\), let \(d(v)\) be the set of darts adjacent to \(v\). Let \(D(\Gamma)\) be the set of all the darts of \(\Gamma\) and suppose that we enumerate the set \(D(\Gamma)\) and that it has \(n\) elements.
With the orientation of the surface and the embedding of the graph in the surface we can produce two permutations:
- A permutation that we denote by \(\sigma\). This permutation is a product of as many cycles as white vertices (that is vertices in \(\Gamma\)). For each vertex consider a small topological circle around it in \(\Sigma\). This circle intersects each adjacent dart once. The circle has an orientation induced by the orientation on \(\Sigma\) and so defines a cycle that sends the number associated to one dart to the number associated to the next dart in the positive orientation of the circle.
- A permutation that we denote by \(\rho\). This permutation is a product of as many \(2\)-cycles as edges has \(\Gamma\). It just tells which two darts belong to the same edge.
Abstract definition
Consider a graph \(\Gamma\) (not a priori embedded in any surface). Now we can again consider one vertex in the interior of each edge splitting each edge in two darts. We label the darts with numbers.
We say that a ribbon structure on \(\Gamma\) is a set of two permutations \((\sigma, \rho)\). Where \(\sigma\) is formed by as many disjoint cycles as vertices had \(\Gamma\). And each cycle is a cyclic ordering of the darts adjacent to a vertex. The permutation \(\rho\) just tell us which two darts belong to the same edge.
For any two such permutations there is a way of “thickening” the graph to a surface with boundary in such a way that the surface retracts (by a strong deformation retract) to the graph and hence the graph is embedded in the surface in a such a way that we could recover \(\sigma\) and \(\rho\).
INPUT:
sigma
– a permutation a product of disjoint cycles of any length; singletons (vertices of valency 1) need not be specifiedrho
– a permutation which is a product of disjoint 2-cycles
Alternatively, one can pass in 2 integers and this will construct a ribbon graph with genus
sigma
andrho
boundary components. Seemake_ribbon()
.One can also construct the bipartite graph modeling the corresponding Brieskorn-Pham singularity by passing 2 integers and the keyword
bipartite=True
. Seebipartite_ribbon_graph()
.EXAMPLES:
Consider the ribbon graph consisting of just \(1\) edge and \(2\) vertices of valency \(1\):
sage: s0 = PermutationGroupElement('(1)(2)') sage: r0 = PermutationGroupElement('(1,2)') sage: R0 = RibbonGraph(s0,r0); R0 Ribbon graph of genus 0 and 1 boundary components
Consider a graph that has \(2\) vertices of valency \(3\) (and hence \(3\) edges). That is represented by the following two permutations:
sage: s1 = PermutationGroupElement('(1,3,5)(2,4,6)') sage: r1 = PermutationGroupElement('(1,2)(3,4)(5,6)') sage: R1 = RibbonGraph(s1, r1); R1 Ribbon graph of genus 1 and 1 boundary components
By drawing the picture in a piece of paper, one can see that its thickening has only \(1\) boundary component. Since the thickening is homotopically equivalent to the graph and the graph has Euler characteristic \(-1\), we find that the thickening has genus \(1\):
sage: R1.number_boundaries() 1 sage: R1.genus() 1
The following example corresponds to the complete bipartite graph of type \((2,3)\), where we have added one more edge \((8,15)\) that ends at a vertex of valency \(1\). Observe that it is not necessary to specify the vertex \((15)\) of valency \(1\) when we define sigma:
sage: s2 = PermutationGroupElement('(1,3,5,8)(2,4,6)') sage: r2 = PermutationGroupElement('(1,2)(3,4)(5,6)(8,15)') sage: R2 = RibbonGraph(s2, r2); R1 Ribbon graph of genus 1 and 1 boundary components sage: R2.sigma() (1,3,5,8)(2,4,6)
This example is constructed by taking the bipartite graph of type \((3,3)\):
sage: s3 = PermutationGroupElement('(1,2,3)(4,5,6)(7,8,9)(10,11,12)(13,14,15)(16,17,18)') sage: r3 = PermutationGroupElement('(1,16)(2,13)(3,10)(4,17)(5,14)(6,11)(7,18)(8,15)(9,12)') sage: R3 = RibbonGraph(s3, r3); R3 Ribbon graph of genus 1 and 3 boundary components
The labeling of the darts can omit some numbers:
sage: s4 = PermutationGroupElement('(3,5,10,12)') sage: r4 = PermutationGroupElement('(3,10)(5,12)') sage: R4 = RibbonGraph(s4,r4); R4 Ribbon graph of genus 1 and 1 boundary components
The next example is the complete bipartite graph of type \((3,3)\), where we have added an edge that ends at a vertex of valency 1:
sage: s5 = PermutationGroupElement('(1,2,3)(4,5,6)(7,8,9)(10,11,12)(13,14,15)(16,17,18,19)') sage: r5 = PermutationGroupElement('(1,16)(2,13)(3,10)(4,17)(5,14)(6,11)(7,18)(8,15)(9,12)(19,20)') sage: R5 = RibbonGraph(s5,r5); R5 Ribbon graph of genus 1 and 3 boundary components sage: C = R5.contract_edge(9); C Ribbon graph of genus 1 and 3 boundary components sage: C.sigma() (1,2,3)(4,5,6)(7,8,9)(10,11,12)(13,14,15)(16,17,18) sage: C.rho() (1,16)(2,13)(3,10)(4,17)(5,14)(6,11)(7,18)(8,15)(9,12) sage: S = R5.reduced(); S Ribbon graph of genus 1 and 3 boundary components sage: S.sigma() (5,6,8,9,14,15,11,12) sage: S.rho() (5,14)(6,11)(8,15)(9,12) sage: R5.boundary() [[1, 16, 17, 4, 5, 14, 15, 8, 9, 12, 10, 3], [2, 13, 14, 5, 6, 11, 12, 9, 7, 18, 19, 20, 20, 19, 16, 1], [3, 10, 11, 6, 4, 17, 18, 7, 8, 15, 13, 2]] sage: S.boundary() [[5, 14, 15, 8, 9, 12], [6, 11, 12, 9, 14, 5], [8, 15, 11, 6]] sage: R5.homology_basis() [[[5, 14], [13, 2], [1, 16], [17, 4]], [[6, 11], [10, 3], [1, 16], [17, 4]], [[8, 15], [13, 2], [1, 16], [18, 7]], [[9, 12], [10, 3], [1, 16], [18, 7]]] sage: S.homology_basis() [[[5, 14]], [[6, 11]], [[8, 15]], [[9, 12]]]
We construct a ribbon graph corresponding to a genus 0 surface with 5 boundary components:
sage: R = RibbonGraph(0, 5); R Ribbon graph of genus 0 and 5 boundary components sage: R.sigma() (1,9,7,5,3)(2,4,6,8,10) sage: R.rho() (1,2)(3,4)(5,6)(7,8)(9,10)
We construct the Brieskorn-Pham singularity of type \((2,3)\):
sage: B23 = RibbonGraph(2, 3, bipartite=True); B23 Ribbon graph of genus 1 and 1 boundary components sage: B23.sigma() (1,2,3)(4,5,6)(7,8)(9,10)(11,12) sage: B23.rho() (1,8)(2,10)(3,12)(4,7)(5,9)(6,11)
-
sage.geometry.ribbon_graph.
bipartite_ribbon_graph
(p, q)¶ Return the bipartite graph modeling the corresponding Brieskorn-Pham singularity.
Take two parallel lines in the plane, and consider \(p\) points in one of them and \(q\) points in the other. Join with a line each point from the first set with every point with the second set. The resulting is a planar projection of the complete bipartite graph of type \((p,q)\). If you consider the cyclic ordering at each vertex induced by the positive orientation of the plane, the result is a ribbon graph whose associated orientable surface with boundary is homeomorphic to the Milnor fiber of the Brieskorn-Pham singularity \(x^p + y^q\). It satisfies that it has \(\gcd(p,q)\) number of boundary components and genus \((pq - p - q - \gcd(p,q) - 2) / 2\).
INPUT:
p
– a positive integerq
– a positive integer
EXAMPLES:
sage: B23 = RibbonGraph(2,3,bipartite=True); B23; B23.sigma(); B23.rho() Ribbon graph of genus 1 and 1 boundary components (1,2,3)(4,5,6)(7,8)(9,10)(11,12) (1,8)(2,10)(3,12)(4,7)(5,9)(6,11) sage: B32 = RibbonGraph(3,2,bipartite=True); B32; B32.sigma(); B32.rho() Ribbon graph of genus 1 and 1 boundary components (1,2)(3,4)(5,6)(7,8,9)(10,11,12) (1,9)(2,12)(3,8)(4,11)(5,7)(6,10) sage: B33 = RibbonGraph(3,3,bipartite=True); B33; B33.sigma(); B33.rho() Ribbon graph of genus 1 and 3 boundary components (1,2,3)(4,5,6)(7,8,9)(10,11,12)(13,14,15)(16,17,18) (1,12)(2,15)(3,18)(4,11)(5,14)(6,17)(7,10)(8,13)(9,16) sage: B24 = RibbonGraph(2,4,bipartite=True); B24; B24.sigma(); B24.rho() Ribbon graph of genus 1 and 2 boundary components (1,2,3,4)(5,6,7,8)(9,10)(11,12)(13,14)(15,16) (1,10)(2,12)(3,14)(4,16)(5,9)(6,11)(7,13)(8,15) sage: B47 = RibbonGraph(4,7, bipartite=True); B47; B47.sigma(); B47.rho() Ribbon graph of genus 9 and 1 boundary components (1,2,3,4,5,6,7)(8,9,10,11,12,13,14)(15,16,17,18,19,20,21)(22,23,24,25,26,27,28)(29,30,31,32)(33,34,35,36)(37,38,39,40)(41,42,43,44)(45,46,47,48)(49,50,51,52)(53,54,55,56) (1,32)(2,36)(3,40)(4,44)(5,48)(6,52)(7,56)(8,31)(9,35)(10,39)(11,43)(12,47)(13,51)(14,55)(15,30)(16,34)(17,38)(18,42)(19,46)(20,50)(21,54)(22,29)(23,33)(24,37)(25,41)(26,45)(27,49)(28,53)
-
sage.geometry.ribbon_graph.
make_ribbon
(g, r)¶ Return a ribbon graph whose thickening has genus
g
andr
boundary components.INPUT:
g
– non-negative integer representing the genus of the thickeningr
– positive integer representing the number of boundary components of the thickening
OUTPUT:
- a ribbon graph that has 2 vertices (two non-trivial cycles in its sigma permutation) of valency \(2g + r\) and it has \(2g + r\) edges (and hence \(4g + 2r\) darts)
EXAMPLES:
sage: from sage.geometry.ribbon_graph import make_ribbon sage: R = make_ribbon(0,1); R Ribbon graph of genus 0 and 1 boundary components sage: R.sigma() () sage: R.rho() (1,2) sage: R = make_ribbon(0,5); R Ribbon graph of genus 0 and 5 boundary components sage: R.sigma() (1,9,7,5,3)(2,4,6,8,10) sage: R.rho() (1,2)(3,4)(5,6)(7,8)(9,10) sage: R = make_ribbon(1,1); R Ribbon graph of genus 1 and 1 boundary components sage: R.sigma() (1,2,3)(4,5,6) sage: R.rho() (1,4)(2,5)(3,6) sage: R = make_ribbon(7,3); R Ribbon graph of genus 7 and 3 boundary components sage: R.sigma() (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,33,31)(16,32,34,17,18,19,20,21,22,23,24,25,26,27,28,29,30) sage: R.rho() (1,16)(2,17)(3,18)(4,19)(5,20)(6,21)(7,22)(8,23)(9,24)(10,25)(11,26)(12,27)(13,28)(14,29)(15,30)(31,32)(33,34)