Ask Your Question

Finding all simply laced Dynkin graphs with a given number of vertices up to isomorphism

asked 2017-10-06 13:49:46 +0200

sagequstions gravatar image

The simply laced Dynkin graphs look as follows and are known from many classification results in mathematics, like Lie algebra or path algebras of finite representaiton type.

Now I try to use SAGE to obtain all possible directed Dynkin quivers with a given number of simples and underlying type. So the input is one of the symbol A, D or E and a natural number $n \geq 2$ and the output should be all directed Dynkin quivers of type X with n points up to isomorphism (where X is A , D or E). The output should have the following form in the example when the input is X=A and n=3:


So the output is a list with 3 entries, which GAP can understand. An entry of the form DynkinQuiver("A",3,["r","l"]) is easy to understand: First A is the type, 3 the number of vertices and ["r","l"] is the orientation (right and left). See on page 14 how the input is for type D and E. Here another example for type E: Q:=DynkinQuiver("E",7,["r","l","r","l","r","u"]).

My motivation is to use SAGE to get this list of quiver and then I want to use the output of SAGE to put it into GAP, where I can do some calculation with the path algebras of those quiver. I want to use SAGE since GAP can not handle problems with graphs and especially is not able to give the list up to isomorphism. Is there a quick way SAGE can find all such directed graphs up to isomorphism and can do the output in the given form? I have a conjecture that might give a new homological characerisation of those Dynkin graphs so Im really curious to test it for a large class of those graphs.

I offer a 30 Euro reward for a fast code that can solve the problem in a quick way maybe until n=12 or 13. I can pay via paypal or Am azon gift card (or donate to an organisation of your choice in case the organisation has paypal payment methods).

edit retag flag offensive close merge delete



Is $E_n$ defined for all $n\geq 6$? Or is it just for $n\in{6,7,8}$?

fidbc gravatar imagefidbc ( 2017-10-06 18:02:42 +0200 )edit

@fidbc It is just defined for n=6,7,8 (or more precisly, it is a Dynkin graph just for those values), but of course it would be no harm to have a generalisation for higher n since one chooses the input number n anyway.

sagequstions gravatar imagesagequstions ( 2017-10-06 18:13:09 +0200 )edit

What exactly do we mean by "fast code"? Any memory usage constraints? Is a 1 minute wait reasonable for $n=13$?

fidbc gravatar imagefidbc ( 2017-10-06 18:27:58 +0200 )edit

Guess the purpose of $E_n$ is having the $n$-th vertex anchored at the third vertex of the path from left to right, correct?

fidbc gravatar imagefidbc ( 2017-10-06 18:29:04 +0200 )edit

@fidbc yes, and 1 minite is of course fine.

sagequstions gravatar imagesagequstions ( 2017-10-06 18:32:02 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2017-10-06 19:12:15 +0200

fidbc gravatar image

Here is some code that might do the job. Please feel free to test it and let me know if this works.

def directg(g6):
    import subprocess
    sp = subprocess.Popen("directg -o", shell=True,
                          stdin=subprocess.PIPE, stdout=subprocess.PIPE,
                          stderr=subprocess.PIPE, close_fds=True)
    stdout = sp.communicate(input='{0}\n'.format(g6))[0]
    d6_strings = stdout.split()
    for d6 in d6_strings:
        yield DiGraph(d6[1:])

def A_base(n):
    return graphs.PathGraph(n).graph6_string()

def D_base(n):
    g = graphs.PathGraph(n-1)
    return g.graph6_string()

def E_base(n):
    g = graphs.PathGraph(n-1)
    return g.graph6_string()

def generate_DynkinQuivers(n,kind='A'):
    if kind not in 'AED':
        raise ValueError("Invalid type of Dynkin quiver, should be one of 'A', 'D' or 'E'.")
    if kind == 'A':
        g6_base = A_base(n)
    elif kind=='D':
        g6_base = D_base(n)
    elif kind=='E':
        g6_base = E_base(n)
    output_template = 'DynkinQuiver("{kind}",{size},[{orientation}])'

    for digraph in directg(g6_base):
        orientation = []
        for i in range(n-2):
            if digraph.has_edge(i,i+1):
            elif digraph.has_edge(i+1,i):
                raise ValueError("Format conversion error.")
        if kind in 'AD':
            if kind=='A':
                other = n-2
                other = n-3
            if digraph.has_edge(other,n-1):
            elif digraph.has_edge(n-1,other):
                raise ValueError("Format conversion error. Last edge of kind {0} quiver.".format(kind))
        if kind =='E':
            if digraph.has_edge(n-1,2):
            elif digraph.has_edge(2,n-1):
                raise ValueError("Format conversion error. Last edge of kind E quiver.")
        yield output_template.format(kind=kind,size=n,orientation=','.join(orientation))
def DynkinQuivers(n,kind='A'):
    return '[{0}]'.format(','.join(generate_DynkinQuivers(n,kind)))

Sample usage:




Which can be saved to a file.

It takes about half a second to go up to n=13

CPU time: 0.41 s, Wall time: 0.53 s
edit flag offensive delete link more


Thank you very much! I will do some tests tonight and then contact you again.

sagequstions gravatar imagesagequstions ( 2017-10-06 19:32:03 +0200 )edit

@fidbc I think its correct. How can I contact you for the price?

sagequstions gravatar imagesagequstions ( 2017-10-07 16:13:12 +0200 )edit

@maresage Would you please be so kind to try and donate via paypal to the address listed here? This info is also available here(They're collecting money for helping repair damage from the quake in Oaxaca). If this is not possible, then donating to sagemath would be nice. You can donate through the top right link at or via this direct link. You may contact me via the fidelbarrera+asksage gmail account for the receipt or to let me know if none of this worked. Thanks!

fidbc gravatar imagefidbc ( 2017-10-08 22:58:45 +0200 )edit

@fidbc I had problems with the first address so I donated it to SAGE. I added your name and the address of the thread in the donation.

sagequstions gravatar imagesagequstions ( 2017-10-17 12:01:59 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-10-06 13:49:46 +0200

Seen: 3,410 times

Last updated: Oct 06 '17