Dual Equivalence Graph Generator -- Sage

The following program is designed to apply Knuth Equivalences and Dual Equivalences, as well as create their related Dual Equivalence Graphs. Several implimentations were tried and tested for time considerations. Below the code is a demonstration of various features of the program.

Introdution: The Knuth Equivalences are a well studied equivalence relation on permutations. More recently, people have begun to look at a dual of this relation. More recently still, people have begun to look at the graph given by this dual as a means. In such a graph, each connected component corresponds to an equivalence class.

The intended application is as follows. It is, in general, a dificult problem to tell if a symmetric function is Schur Positive (has nonneggative integer coefficients over the basis of Schur functions). By moving to the broader basis of Elementary Quasi-symmetric functions, which are provide easier closed formulas, we hope to come up with a simpler criterion for Schur positivity. Though we are graphing permutations, each of these permutations corresponds to an elementary quasisymmetric function, and each connected component corresponds to a schur function. The problem then translates into whether a graph on quasisymmetrics can transformed into these nice components, which can be couned in non-negative intergers.

There is more explanation below.

#auto %cython ###Package of DEG functions## from sage.all import Graph, copy, partitions ##Turns Integers and Tuples to Lists##Called by other functions## def IntToList(x): cdef list y if type(x) is tuple: y=list(x) elif type(x) is not list: y=[]; x=str(x) ###turning sage int to list. Returns list for k in range(0, len(x)): y.append(int(x[k])) return y else: return x ####################################### ##Standard Dual Equivalence Functions## ####################################### ####Elementary Knuth Equivalence## ##Not necssary for other functions## def KnuthEq(x,i): ##### Warning! Only programmed for permutations. No repeat entries! cdef list y cdef int z if type(x) is not list: y=IntToList(x) else: y=copy(x) if len(y) < i+1: print "Not defined for i > len(y)-1" return elif i<2: print "Not defined for i < 2" return else: if y[i-2]<y[i-1]<y[i] or y[i-2]>y[i-1]>y[i]: return y elif y[i-1]<y[i]<y[i-2] or y[i-1]>y[i]>y[i-2]: z= y[i-2] y[i-2]= y[i-1]; y[i-1]=z return y else: #y[i-1]<y[i-2]<y[i] or y[i-1]>y[i-2]>y[i] z= y[i] y[i]= y[i-1]; y[i-1]=z return y ###Elementary Dual Equivalence!### #####only defined for permutations#### def DualEq(x,i): cdef list y,w if type(x) is not list: y=IntToList(x) else: y=copy(x) ## a=y.index(i-1) b=y.index(i) c=y.index(i+1) if a<b<c or a>b>c: return y elif b<c<a or b>c>a: del(y[b]); y.insert(b,i-1) del(y[a]); y.insert(a,i) return y else: #y[i-1]<y[i-2]<y[i] or y[i-1]>y[i-2]>y[i] del(y[b]); y.insert(b,i+1) del(y[c]); y.insert(c,i) return y #######Dual Equivalence Graph from permutation###### ###Elementary Dual Equivalence (LLT version)### #####only defined for permutations#### def DualEq_LLT(x,i,content,k): cdef list y content=IntToList(content) y=copy(x) if type(y) is not list: y=IntToList(y) ## a=y.index(i-1) b=y.index(i) c=y.index(i+1) if a<b<c or a>b>c: return y elif b<c<a or b>c>a: if content[a]-content[b]>k or content[b] - content[a]>k: del(y[b]); y.insert(b,i-1) del(y[a]); y.insert(a,i) return y else: del(y[c]); y.insert(c,i-1) del(y[b]); y.insert(b,i+1) del(y[a]); y.insert(a,i) return y else: if content[c]-content[b]>k or content[b] - content[c]>k: del(y[b]); y.insert(b,i+1) del(y[c]); y.insert(c,i) return y else: del(y[c]); y.insert(c,i) del(y[b]); y.insert(b,i-1) del(y[a]); y.insert(a,i+1) return y ##Giving input as integer yields cleaner plot, but for input longer than 9, need list or tuple!## ##Common error: all inputs must be permutations, not just a words. def DEG(x, Single_Edge = False): cdef list New_Vertices, u OriginalType=type(x) if OriginalType is not list: x=IntToList(x) ##Turning list to int or string if input is into or list resp. for display## def ListToLabel(L): cdef int N if OriginalType is tuple: return tuple(L) elif OriginalType is list: return tuple(L) else: N = 0 for i in range(0,len(L)): N+= L[i]*10**(len(L)-1-i) return N ### Making Graph ####### ##With Doubled Edges## if Single_Edge == False: G=Graph(multiedges= True); G.add_vertex(ListToLabel(x)) New_Vertices=[x] while len(New_Vertices) > 0: Length = len(New_Vertices) for X in New_Vertices: for i in range(2,len(x)): u=DualEq(X,i) v=ListToLabel(u) w=ListToLabel(X) if v not in G.vertices(): New_Vertices.append(u) G.add_edge(v,w,i) if (w, v, i) not in G.edges() and (v, w, i) not in G.edges(): G.add_edge(v,w,i) for i in range(1,Length+1): del(New_Vertices[0]) ##With Single_Edge##Simpler graph, usually slightly faster, double edges not shown## else: G=Graph(); G.add_vertex(ListToLabel(x)) New_Vertices=[x] while len(New_Vertices) > 0: Length = len(New_Vertices) for X in New_Vertices: for i in range(2,len(x)): u=DualEq(X,i) v=ListToLabel(u) w=ListToLabel(X) if v not in G.vertices(): New_Vertices.append(u) if (w, v) not in G.edges(labels=False) and (v,w) not in G.edges(labels=False): if i<len(x)-1: if DualEq(X,i+1) == DualEq(X,i): G.add_edge(v,w,(i,i+1)) else: G.add_edge(v,w,i) else: G.add_edge(v,w,i) for i in range(1,Length+1): del(New_Vertices[0]) return(G) ##################################### ##LLT Version of Dual Equivalence#### ##Less well behaved## ##################################### ##Giving input as integer yields cleaner plot, but for input longer than 9, need list or tuple!## ##Common error: all inputs must be permutations, not just a words. ###Elementary Dual Equivalence!### ###only defined for permutations#### ###Non-Standard Def!. 'content' defines when to use d^~, when all 3 entries are in a range [j,content[j]]### def DualEq_LLT(x,i,content): cdef list y content=IntToList(content) y=copy(x) if type(y) is not list: y=IntToList(y) ## a=y.index(i-1) b=y.index(i) c=y.index(i+1) if a<b<c or a>b>c: return y elif b<c<a or b>c>a: if min(content[a],content[b]) <= max(a,b): del(y[b]); y.insert(b,i-1) del(y[a]); y.insert(a,i) return y else: del(y[c]); y.insert(c,i-1) del(y[b]); y.insert(b,i+1) del(y[a]); y.insert(a,i) return y else: if min(content[b],content[c]) <= max(b,c): del(y[b]); y.insert(b,i+1) del(y[c]); y.insert(c,i) return y else: del(y[c]); y.insert(c,i) del(y[b]); y.insert(b,i-1) del(y[a]); y.insert(a,i+1) return y #######Dual Equivalence Graph from permutation###### ##Giving input as integer yields cleaner plot, but for input longer than 9, need list or tuple!## ##Common error: all inputs must be permutations, not just a words. def DEG_LLT(x, content, Single_Edge = False): cdef list New_Vertices, u content=IntToList(content) OriginalType=type(x) if OriginalType is not list: x=IntToList(x) ##Turning list to int or string if input is into or list resp. for display## def ListToLabel(L): cdef int N if OriginalType is tuple: return tuple(L) elif OriginalType is list: return tuple(L) else: N = 0 for i in range(0,len(L)): N+= L[i]*10**(len(L)-1-i) return N ### Making Graph ####### ##With Doubled Edges## if Single_Edge == False: G=Graph(multiedges= True); G.add_vertex(ListToLabel(x)) New_Vertices=[x] while len(New_Vertices) > 0: Length = len(New_Vertices) for X in New_Vertices: for i in range(2,len(x)): u=DualEq_LLT(X,i,content) v=ListToLabel(u) w=ListToLabel(X) if v not in G.vertices(): New_Vertices.append(u) G.add_edge(v,w,i) if (w, v, i) not in G.edges() and (v, w, i) not in G.edges(): G.add_edge(v,w,i) for i in range(1,Length+1): del(New_Vertices[0]) ##With Single_Edge##Simpler graph, usually slightly faster, double edges not shown## else: G=Graph(); G.add_vertex(ListToLabel(x)) New_Vertices=[x] while len(New_Vertices) > 0: Length = len(New_Vertices) for X in New_Vertices: for i in range(2,len(x)): u=DualEq_LLT(X,i,content) v=ListToLabel(u) w=ListToLabel(X) if v not in G.vertices(): New_Vertices.append(u) if (w, v) not in G.edges(labels=False) and (v,w) not in G.edges(labels=False): if i<len(x)-1: if DualEq_LLT(X,i+1,content) == DualEq_LLT(X,i,content): G.add_edge(v,w,(i,i+1)) else: G.add_edge(v,w,i) else: G.add_edge(v,w,i) for i in range(1,Length+1): del(New_Vertices[0]) return(G) ###################################################################### ##Functions for creating representative words of equivalence classes## ###################################################################### def Rep_Word(x): #Input Partition, return maximal word. cdef list Word cdef int Size Word=[]; Size=sum(x) for i in range(0, len(x)): for k in range(Size-x[i]+1, Size+1): Word.append(k) Size=Size-x[i] return Word def All_Rep_Words(n): ##Gives a representative reduced word for each partition on n cdef list Words Words=[] for x in partitions(n): Words.append(Rep_Word(x)) return Words

__home_com..._6_code_sage2_spyx.c __home_com...code_sage2_spyx.html __sagenb_s...15_code_sage2_spyx.c __sagenb_s...code_sage2_spyx.html

We have acually already saved some graphs in dictionaries that we will call later.

#auto SE_DEGs=load(DATA+'SE_DEGs') SE_LLTs5=load(DATA+'SE_LLTs5') SE_LLTs6=load(DATA+'SE_LLTs6')

We will now demo some of the capabilities. First, the Knuth and dual equivalences act as either the identity or as a transposition on permutations. The inputs are a permutation and a number $i$ in $2\leq i \leq n-1$. See if you can figure out the rule being applied.

print KnuthEq(21354,2), KnuthEq(21354,3), KnuthEq(21354,4) print DualEq(21354,2), DualEq(21354,3), DualEq(21354,4)

[2, 3, 1, 5, 4] [2, 1, 3, 5, 4] [2, 1, 5, 3, 4]
[3, 1, 2, 5, 4] [2, 1, 3, 5, 4] [2, 1, 4, 5, 3]

[2, 3, 1, 5, 4] [2, 1, 3, 5, 4] [2, 1, 5, 3, 4]
[3, 1, 2, 5, 4] [2, 1, 3, 5, 4] [2, 1, 4, 5, 3]

All of these functions have been designed to accept integers, lists, and tuples, though large permutations do not accept integers due to ambiguities witht two digit numbers.

print KnuthEq([2,1,3,5,4],2), KnuthEq((2,1,3,5,4),3), KnuthEq(21354,4) print DualEq([2,1,3,5,4],2), DualEq((2,1,3,5,4),3), DualEq(21354,4) print DualEq([1,2,3,4,5,6,7,8,9,10,11],4) print DualEq(1234567891011,4) ##Does not work! Programming an exceptions would be good if distributed to general audience.

[2, 3, 1, 5, 4] [2, 1, 3, 5, 4] [2, 1, 5, 3, 4]
[3, 1, 2, 5, 4] [2, 1, 3, 5, 4] [2, 1, 4, 5, 3]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1]

[2, 3, 1, 5, 4] [2, 1, 3, 5, 4] [2, 1, 5, 3, 4]
[3, 1, 2, 5, 4] [2, 1, 3, 5, 4] [2, 1, 4, 5, 3]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1]

The key feature of the program is that it generates Dual Equivalence Graphs. That is, if you give it a permutation, it will apply all dual equivalences to get new vertices attached by edges labeled by the $i$ value of the equivalence. It then repeats the process on the new vertices to generate the entire connected component. Again, this has been programmed to accept integers, lists, and tuples.

DEG(53412).show(edge_labels=true); DEG([5,4,1,2,3]).show(edge_labels=true)

These graphs can get quite complicated, so it is very helpful that sage has several built in features to change how they are displayed.

It is sometimes helpful to clean up the graphs further by eliminating double edges. Additionally, some functionality of sage does not work on multi-edge graphs. Plus, single edge graphs are cleaner looking and usually faster to create.

DEG(3412).show(edge_labels=true) DEG(3412,Single_Edge=true).show(edge_labels=true)

The difference is more striking for larger graphs. (The following cell takes a minute or two to run.)

DEG([4,7,2,6,9,10,1,3,5,8]).plot(color_by_label=true, vertex_size=5, iterations=500, vertex_labels=false);DEG([4,7,2,6,9,10,1,3,5,8], Single_Edge=True).plot(color_by_label=true, vertex_size=5, iterations=500, vertex_labels=false)

We may employ another function to produce complete lists of graphs quickly. Below are all degree 7 graphs (which may have never been produced in entirety before this). That is, below is a complete partition of $S_n$ into its dual equivalence classes in graph form. Again, a presaved dictionary would be faster, but this lets us demonstrate a useful function that can be utilized for any degree.

ListOfGraphs=[] for w in All_Rep_Words(7): ##All_Rep_Words was defined in earlier cell for this purpose.## Temporary= DEG(w,Single_Edge=True) ListOfGraphs.append(Temporary) graphs_list.show_graphs(ListOfGraphs,layout='spring', iterations=1000,vertex_size=3)

For speedy future tests, we also save small degree graphs in a dictionary, which are saved to the worksheet and automatically loaded upon opening. This is a good example of how to use the functions partitions (built into sage) and Rep_Word (part of this worksheet) to make a single representative word for each isomorphism type. It may also be helpful to realize that SE_DEG tends to run faster thatn DEG. Also, multi-edge graphs do not save correctly without adding a patch to save. For this reason, they are not currently saved to the worksheet.

#SE_DEGs={} ###long time #for i in range(1,10): # for x in partitions(i): # SE_DEGs[x]=DEG(Rep_Word(x), Single_Edge=True) #save(SE_DEGs, DATA+'SE_DEGs')

#DEGs={} ##This will not pickle correctly without patch! ###long time #for i in range(1,10): # for x in partitions(i): # DEGs[x]=DEG(Rep_Word(x)) #save(DEGs, DATA+'DEGs')

SE_DEGs[(1,2,3,3)]

Graph on 168 vertices

Graph on 168 vertices

We may also use sage to test standard graph properties.

DEG(5234176).is_bipartite() #Conjecture that all DEG are bipartite?

True

True

DEG(65187234).is_planar() #all degree 7 DEGs are planar

False

False

DEGs have been checked to be bipartite up to degree 9. Below is a bit of code for testing such things, but really, one of the premade dictionaries could speed this up for degree less than or equal to 9.

Passing=True for w in All_Rep_Words(5): #if w[0] == 10 and w[9] == 5: Sad= DEG(w) if Sad.is_bipartite()==False: print 'Oh NO!' print w Passing=False break print w, 'passes!' if Passing==True: print 'They all passed!'

[5, 4, 3, 2, 1] passes!
[5, 4, 3, 1, 2] passes!
[5, 3, 4, 1, 2] passes!
[5, 4, 1, 2, 3] passes!
[4, 5, 1, 2, 3] passes!
[5, 1, 2, 3, 4] passes!
[1, 2, 3, 4, 5] passes!
They all passed!

[5, 4, 3, 2, 1] passes!
[5, 4, 3, 1, 2] passes!
[5, 3, 4, 1, 2] passes!
[5, 4, 1, 2, 3] passes!
[4, 5, 1, 2, 3] passes!
[5, 1, 2, 3, 4] passes!
[1, 2, 3, 4, 5] passes!
They all passed!

Finally, we should point out that work is being done on a more general version of dual equivalence, which we will call LLT Dual Equivalence for reasons that do not matter to the casual reader. This dual equivalence takes an extra input of a weekly increasing word $w$ such that $w_i \geq i+1$ exept for the last entry $w_n=n.$ (Even this definition of LLT dual equivalence is not quite standardized.)

DualEq_LLT([2,1,3,4],2,[3,3,4,4])

[1, 3, 2, 4]

[1, 3, 2, 4]

The process is more computationally heavy, but we may make and save lists as before. Again, the SE_LLTs are a bit faster to generate. Regaurdless, the computational time grows quickly. LLTs5 takes about 16 seconds of wall time. Moving up to 7 would probably put the computation time around a day or two.

#%time #LLTs6=[] #for i in range(2,7): # for j in range(max(i,3),7): # for k in range(max(j,4),7): ###These number of entries in these nested loops are esentially Catalan numbers # for l in range(max(k,5),7): # for w in SymmetricGroup(6): # w=w.list() # if w[0]<6: # checker=false # New_Graph= DEG_LLT(w,[i,j,k,l,6,6],Single_Edge=false) # for G in LLTs6: # if G.is_isomorphic(New_Graph,edge_labels=true)==true: # checker=true # break # if checker==false: # LLTs6.append(New_Graph) # print i #save(LLTs6,DATA+'LLTs6')

2
3
4
5
6
CPU time: 2113.59 s,  Wall time: 2367.74 s

2
3
4
5
6
CPU time: 2113.59 s,  Wall time: 2367.74 s

We have just made all degree 6 LLT DEGs. Infact several other dictionaries, LLTs5, SE_LLTs5, and SE_LLTs6, are also saved to this worksheet and automatically loaded upon opening the worksheet.

print len(LLTs5), len(SE_LLTs5), len(LLTs6), len(SE_LLTs6)

13 13 88 88

13 13 88 88

We do not have an easy way of calling a particular graph type in this case, so we must simply call them by the number in which they appeared in the above algorithm.

SE_LLTs6[81].plot(color_by_label=false, vertex_labels=false,vertex_size=5,iterations=10000)

We end with what is probably the first ever display of all degree 6 LLT Dual Equivalence Graphs. There is an open question of whether all LLT Dual Equivalence graphs can be turned into standard dual equivalence graphs by "acceptable" modifications to the edge sets. At this point, it is possible (if unlikely) that a counter example is displayed below.

graphs_list.show_graphs(LLTs6,layout='spring',vertex_size=5,edge_labels=false,iterations=1000)

This concludes the walk through. We hope you found it fun, eductional, and utilitarian. If nothing else, there seems to be promise as a Warshak test generator.

Dual Equivalence Graph Generator

4461 days ago by comphy