Stable graphs.ipynb

Kernel: SageMath 9.0

Using admcycles it is possible to compute lists of stable graphs using the function list_strata(g,n,e). It returns a list of isomorphism classes of stable graphs in genus g with n legs and e edges.

Execute the commands below by selecting them with the mouse and pressing Shift+Enter.

from admcycles import *  # loads the package admcycles
L = list_strata(1,2,1)   # computes list of stable graphs with g=1, n=2 and e=1 edge
for Gamma in L:
    print(Gamma)         # prints all graphs

A stable graph is represented by three lists:

• a list of the genera of the vertices

• for each vertex the list of half-edges incident to the vertex

• a list of pairs of half-edges which are connected by an edge; half-edges named 1,...,n are the legs of the graph

So the stable graph [0, 1] [[1, 2, 3], [4]] [(3, 4)] has two vertices (of genus 0 and 1, respectively). The genus 0 vertex has half-edges 1,2,3 and the genus 1 vertex has a half-edge 4. The half-edges 3,4 form an edge.

In the standard language of stable graphs you would say that the graph above is given by

• V = {v_1, v_2}, g(v_1) = 0, g(v_2) = 1

• H = {1,2,3,4}, v(1) = v_1, v(2) = v_1, v(3) = v_1, v(4) = v_2

• L = {1,2}, $\ell$ : L $\to$ {1,2}, $\ell$(1) = 1, $\ell$(2) = 2

• $\iota$ : H $\to$ H, $\iota$(1)=1, $\iota$(2)=2, $\iota$(3)=4, $\iota$(4)=3

We can also input a stable graph by giving three lists as above, for instance to compute the number of its automorphisms.

Gamma = StableGraph([1,1,1],[[1,6],[2,3],[4,5]],[(1,2),(3,4),(5,6)])  # Gamma = triangle of vertices of genus 1
Gamma.automorphism_number()                                           # Aut(Gamma) = ?

If we want to list all strata of a given genus and number of markings, we can use the following function.

def all_strata(g,n):
    return sum((list_strata(g,n,e) for e in range(0,3*g-3+n+1)),[])
# Exercise (if you know Python): Understand why the above function does what we want.

L = all_strata(1,2)
for Gamma in L:
    print(Gamma)         # prints all graphs

One thing we can check is that the number of stable graphs grows extremely fast as g,n increase.

for n in range(1,6):
    print('The number of stable graphs with g=1, n='+repr(n)+' is equal to '+repr(len(all_strata(1,n))))