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).
For example:
|
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.
CPU time: 13.96 s, Wall time: 14.29 s CPU time: 13.96 s, Wall time: 14.29 s |
Here are all of the degree 6 dual equivalence graphs displayed visually.
|
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$.
CPU time: 225.37 s, Wall time: 225.91 s 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.
True True True True True True True True True True True True |
It is also easy to verify visually.
|
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.
CPU time: 2.23 s, Wall time: 13.01 s CPU time: 2.23 s, Wall time: 13.01 s |
Again, these can be easily checked visually below.
|
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') .
CPU time: 834.50 s, Wall time: 1874.64 s 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)}$.
 
|
Below is a close up of the fifth graph, just to verify that it is isomorphic to $\mathcal{G}_{(3,2,1)}$.
|
Because axioms 1,2,3,$4^+$, and 5 are satisfied, we must have a dual equivalence gaph, completing our proof.
|
|