All published worksheets from http://sagenb.org
Image: ubuntu2004
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 , labeled x in the code, and a weakly increasing word labeled 'content' in the code. If we let content, then should satisfy and . The function then returns . Here, is labeled by DualEq_LLT(x,i,content). It uses if and are in some range . Otherwise, is employed. By using 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 and then applies 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 . Because each contains only two numbers, will always act as , creating a standard dual equivalence graph.
Here are all of the degree 6 dual equivalence graphs displayed visually.
The next cells verify the following lemma:
"Given a fixed value of and some weakly increasing shifted content for the indices from 1 to , let be any connected signed colored graph with vertex set and edge sets defined by the action of for all . Further suppose never acts on nontrivially via unless and have adjacent indices. Then is a dual equivalence graph."
Because obeys axioms 1,2,3, and 5, it is sufficient to check axiom . We do this by naively checking every permutation in and saving each new isomorphism type into a list labeled "LLTs6_SmallContent". The condition on the action of can be realized by the added constraint .
The next cell checks that the isomorphism types above are in fact dual equivalence graphs.
It is also easy to verify visually.
The next series of cells are used to prove the following lemma:
"Let be a tuple of skew shapes with content width less than 3, and let be any connected component of the graph on SYT with edges given by . Then is a dual equivalence graph."
Edges given by obey axioms 1,2, 3, and 5, so we begin by showing that obeys axiom 4. It suffices to check all such of degree 5. The previous lemma takes care of all that do not have some . By symmetry, we may assume . It is easily checked that width( implies that cannot be 45555 or 55555. Thus, we need only check (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 if width( and : 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.
Again, these can be easily checked visually below.
We now check axiom . Recall that in the presence of axioms 1,2,3,4, and 5, we may check axiom by showing that no 4-color component can be found in a specific family of graphs . Visually, this family looks like large loops corresponding to muliple copies of . When presented in the 'Single_Edge=true' format, which records double edges as a single edge labeled by a pair , 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 .
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') .
Now a visual check shows that the only graphs with no leaves (the first and fifth graphs in the list) are isomorphic to either , or .
Below is a close up of the fifth graph, just to verify that it is isomorphic to .
Because axioms 1,2,3,, and 5 are satisfied, we must have a dual equivalence gaph, completing our proof.