4715.sagews

Below are computer proofs that certain signed colored graphs are dual equivalence graphs. While many of these proof could be run faster, we chose to focus on simplicity and transparancy. For an expanded set of functions and a quick tour of the functionality, see http://www.sagenb.org/home/pub/4714/.

In the first cell we define a function that takes takes a permutation in $S_n$, labeled x in the code, and a weakly increasing word labeled 'content' in the code.  If we let $\tau=$content, then $\tau$ should satisfy $\tau_j \geq j, \tau_{j+1} \geq \tau_j,$ and $\tau_j \leq n$. The function then returns $D_i(x)$. Here, $D_i$ is labeled by DualEq_LLT(x,i,content). It uses $\tilde d_i$ if $i-1, i,$ and $i+1$ are in some range $[j, \tau_j]$. Otherwise, $d_i$ is employed. By using $\tau$ instead of appealing directly to the shifted content, we may reduce many problems to checking a finite number of graphs.

The function DEG_LLT(x, content) is defined in the same cell. It starts at a vertex $x$ and then applies $D_i$ repeatedly to create a graph. The signatures are not included, but could be determined from the permutations. The graphs necessarily obey axioms 1 and 2, and so the signatures may also be recovered from the edge structure (up to multiplying all signatures by -1).

#auto
%cython
################################################
###Package of Dual Equivalence Graph functions##
################################################

from sage.all import Graph, copy, partitions



##A preliminary function that turns Integers and Tuples to Lists#
##This is 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


    
#####################################
##LLT Version of Dual Equivalence####
#####################################



###Modified Dual Equivalence (D_i)###
             ##Accepts integers, but for input longer than 9 it requires list or tuple!##
             ##Common error: all inputs must be permutations, not just words.##
             ##'content' defines when to use d^~. i.e. 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 a permutation######
             ##Applies DualEq_LLT repeatedly to find all vertices of a graph##
             ##Single_Edge option expresses double edges as a single edge labeled by (i, i+1).
             ##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)

For example:

DEG_LLT(4261573,2467777).plot(vertex_size=5,color_by_label=true, iterations=2000)

Here, we have chosen to turn edge labels into colors for a cleaner image. Below, we will also omit vertex labels.

The next cell generates all degree 6 dual equivalnce graphs (up to multiplying all signatures by -1) by choosing $\tau = 234566$. Because each $[i,\tau_i]$ contains only two numbers, $D_i$ will always act as $d_i$, creating a standard dual equivalence graph.

%time
DEGs6=[]
for w in SymmetricGroup(6):
    w=w.list()
    checker=false
    New_Graph= DEG_LLT(w,[2,3,4,5,6,6],Single_Edge=false)
    for G in DEGs6:
        if G.is_isomorphic(New_Graph,edge_labels=true)==true:
            checker=true
            break
    if checker==false:
        DEGs6.append(New_Graph)

CPU time: 13.96 s, Wall time: 14.29 s

Here are all of the degree 6 dual equivalence graphs displayed visually.

graphs_list.show_graphs(DEGs6,layout='spring', color_by_label=true, iterations=4000,vertex_size=2)

The next cells verify the following lemma:

"Given a fixed value of $k$ and some weakly increasing shifted content for the indices from 1 to $n$, let $\mathcal{G}$ be any connected signed colored graph with vertex set $S \subset S_n$ and edge sets $E_i$ defined by the action of $D_i$ for all $2\leq i \leq n-1$. Further suppose $D_i$ never acts on $S$ nontrivially via $\tilde d_i$ unless $i-1, i,$ and $i+1$ have adjacent indices. Then $\mathcal{G}$ is a dual equivalence graph."

Because $D_i$ obeys axioms 1,2,3, and 5, it is sufficient to check axiom $4^+$. We do this by naively checking every permutation in $S_6$ and saving each new isomorphism type into a list labeled "LLTs6_SmallContent". The condition on the action of $D_i$ can be realized by the added constraint $\tau_i \leq i+2$.

%time
LLTs6_SmallContent=[]
for i in range(2,4):
    for j in range(3,5):
        for k in range(4,6):
            for l in range(5,7):
                for w in SymmetricGroup(6):
                    w=w.list()
                    checker=false
                    New_Graph= DEG_LLT(w,[i,j,k,l,6,6],Single_Edge=false)
                    for G in LLTs6_SmallContent:
                        if G.is_isomorphic(New_Graph,edge_labels=true)==true:
                            checker=true
                            break
                    if checker==false:
                        LLTs6_SmallContent.append(New_Graph)

CPU time: 225.37 s, Wall time: 225.91 s

The next cell checks that the isomorphism types above are in fact dual equivalence graphs.

for G in LLTs6_SmallContent:
    Checker=False
    for H in DEGs6:    
        if G.is_isomorphic(H,edge_labels=true)==true:
             Checker=True
    print Checker

True True True True True True

It is also easy to verify visually.

graphs_list.show_graphs(LLTs6_SmallContent,layout='spring', color_by_label=true, iterations=4000,vertex_size=2)

The next series of cells are used to prove the following lemma:

"Let $\mu$ be a tuple of skew shapes with content width less than 3, and let $\mathcal{G}$ be any connected component of the graph on SYT$(\mu)$ with edges given by $D_i$. Then $\mathcal{G}$ is a dual equivalence graph."

Edges given by $D_i$ obey axioms 1,2, 3, and 5, so we begin by showing that $\mathcal{G}$ obeys axiom 4.  It suffices to check all such $\mu$ of degree 5.  The previous lemma takes care of all $\tau$ that do not have some $\tau_i - i \geq 4$. By symmetry, we may assume $\tau_1 = 4$. It is easily checked that width($\mu)\leq 2$ implies that $\tau$ cannot be 45555 or 55555. Thus, we need only check $\tau \in \{44455, 44555\}$ (44455 is actually impossible as well, but we leave it in because it will not effect our results).

The reader is also left to check that the following words cannot be fillings of $\mu$ if width($\mu) \leq 2$ and $\tau_1=4$: 21435, 34125, 32541, and 45231. Specifically, this is the set of words that would lead to a violation of axiom 4 in the two color component when we restrict to the first four values of the word.

%time
Forbidden=[(2,1,4,3,5),(3,4,1,2,5),(3,2,5,4,1),(4,5,2,3,1)] ##impossible words if width<=2 and tau ('content') starts with 4.##

LLTs5_Width2=[]
for i in range(4,6):
        for w in SymmetricGroup(5):
                    w=w.list()
                    checker=false
                    New_Graph= DEG_LLT(w,[4,4,i,5,5],Single_Edge=false)
                    for G in LLTs5_Width2:
                        if G.is_isomorphic(New_Graph,edge_labels=true)==true:
                            checker=true
                            break        
                    if checker==false:
                        for F in Forbidden:
                            if F in New_Graph.vertices():
                                checker=true
                                break
                    if checker==false:
                        LLTs5_Width2.append(New_Graph)

CPU time: 2.23 s, Wall time: 13.01 s

Again, these can be easily checked visually below.

graphs_list.show_graphs(LLTs5_Width2,layout='spring', color_by_label=true, iterations=4000,vertex_size=2)

We now check axiom $4^+$. Recall that in the presence of axioms 1,2,3,4, and 5, we may check axiom $4^+$ by showing that no 4-color component can be found in a specific family of graphs $\mathcal{F}$. Visually, this family looks like large loops corresponding to muliple copies of $\mathcal{G}_{(3,2,1)}$. When presented in the 'Single_Edge=true' format, which records double edges as a single edge labeled by a pair $(i, i+1)$, we need only look for graphs that have no leaves. By only checking for this disallowed family, we may run a very naive program that will test many cases that may not correpond to a filling of some appropriate $\mu$.

Note: For those running this as an active worksheet, the output of the following cell is saved to the file and can be accesed by running LLTs6_Width2=load(DATA+'LLTs6_Width2') .

%time
LLTs6_Width2=[]
for i in range(2,5):
    for j in range(max(i,3),6):
        for k in range(max(j,4),7):
            for l in range(max(k,5),7):
                    for w in SymmetricGroup(6):
                        w=w.list()
                        checker=false
                        New_Graph= DEG_LLT(w,[i,j,k,l,6,6],Single_Edge=true)
                        for G in LLTs6_Width2:
                            if G.is_isomorphic(New_Graph)==true:
                                checker=true
                                break
                        if checker==false:
                            LLTs6_Width2.append(New_Graph)

CPU time: 834.50 s, Wall time: 1874.64 s

Now a visual check shows that the only graphs with no leaves (the first and fifth graphs in the list) are isomorphic to either $\mathcal{G}_{(6)}$, $\mathcal{G}_{(1,1,1,1,1,1)}$ or $\mathcal{G}_{(3,2,1)}$.

graphs_list.show_graphs(LLTs6_Width2,layout='spring', iterations=4000,vertex_size=2)

Below is a close up of the fifth graph, just to verify that it is isomorphic to $\mathcal{G}_{(3,2,1)}$.

LLTs6_Width2[4].show(figsize=[6,6],vertex_size=2, vertex_labels=false, edge_labels=true, iterations=5000)

Because axioms 1,2,3,$4^+$, and 5 are satisfied, we must have a dual equivalence gaph, completing our proof.