Implement dual equivalence graphs

[tscrim]

Implement methods for dual equivalence graphs coming from standard tableaux of a fixed shape and as weight 0 crystal spaces.

Depends on #18032

CC: @sagetrac-sage-combinat @anneschilling @darijgr @sagetrac-troby

Component: combinatorics

Keywords: dual equivalence graphs, sd67

Author: Travis Scrimshaw

Branch/Commit: 7594b95

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/18050

[tscrim]

Commit: ae0e900

[tscrim]

New commits:

ae0e900

Implement dual equivalence graph methods.

[tscrim]

Branch: public/crystals/dual_equivalence-18050

[sagetrac-git]

Changed commit from ae0e900 to c1b3637

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c1b3637

Fixing a bug so that isolated vertices are included.

[fchapoton]

comment:4

some failing doctests, see patchbot report

[darijgr]

comment:5

In other news, here's something I've been long since curious about:

+ - :meth:`~sage.categories.regular_crystals.RegularCrystals.ParentMethods.dual_equivalence_graph`
+ - :meth:`sage.combinat.partition.Partition.dual_equivalence_graph`

What is the difference between the syntax with the tilde and that without?

[tscrim]

comment:6

The tilde only displays the last thing after a dot, without displays the entire path.

[darijgr]

comment:7

Ah, thank you!

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

274a018

Fixing doctest (because I'm stupid) and added directed options.

[sagetrac-git]

Changed commit from c1b3637 to 274a018

[darijgr]

comment:10

Stupid question:

Assuming that your dual equivalence graph is the graph \mathcal{G}(\mathcal{X}) defined in Section 4 of the Assaf preprint you are citing, is your condition \varepsilon_j(b) = \varphi_j(b) really equivalent to her (4.1) ? If so, what are the connections between your \varepsilon and \varphi and her \varepsilon and \delta?

[tscrim]

comment:11

The \varepsilon_j(b) = \varphi_j(b) comes from the crystal axiom \varphi_j(b) = \varepsilon_j(b) + wt(b) (wt is the weight) and we are looking at the wt(b) = 0 elements. Her \varepsilon is the same as mine and the \delta is something related but slightly different (see towards the beginning of section 2).

[mantepse]

comment:12

I think the docstring of Partition.dual_equivalence_graph could be clearer. I suggest

Two permutations `p` and `q` differ by an elementary dual Knuth
relation (of color `i`), when, in one line notation, the letter
`i` does not occur between `i-1` and `i+1`, and `q` is obtained 
from `p` by switching the places of `i-1` and `i+1`.

Two standard Young tableaux of shape `\lambda` differ by an
elementary dual Knuth relation (of color `i`), if their content
reading words differ by an elementary dual Knuth relation (of
color `i`).

The *dual equivalence graph* is the edge-colored graph formed by
the set of standard Young tableaux of shape `\lambda` where edges
colored by `i` are given by dual equivalences of color `i`.

[darijgr]

comment:13

Replying to @tscrim:

The \varepsilon_j(b) = \varphi_j(b) comes from the crystal axiom \varphi_j(b) = \varepsilon_j(b) + wt(b) (wt is the weight) and we are looking at the wt(b) = 0 elements. Her \varepsilon is the same as mine and the \delta is something related but slightly different (see towards the beginning of section 2).

Oh. Is \delta_j(b) the same as your -\varphi_j(b)? And what does the = 0 or 1 part of Assaf's (4.1) correspond to in your definition?

[tscrim]

comment:14

Replying to @darijgr:

Oh. Is \delta_j(b) the same as your -\varphi_j(b)?

Yes.

And what does the = 0 or 1 part of Assaf's (4.1) correspond to in your definition?

It means that we can do the e_i operation exactly 0 or 1 times before it falls off the crystal graph. In other words, these conditions state that if there is an i-arrow in the crystal graph going through b, then the entire chain of i-arrows containing b has length 2 with b in the middle.

@mantepse I will make those changes in a minute.

[sagetrac-git]

Changed commit from 274a018 to 63c7027

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

63c7027

Changed the wording of docstring for DEG in partition.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2ad1a17	correct a few typos in crystals doc, and make notations consistent (phi and epsilon become varphi and varepsilon)
6c70848	some more, hopefully correct, doc fixes
65ddba1	review of the changes in sage/combinat/partition.py

[sagetrac-git]

Changed commit from 5216085 to 9868571

[sagetrac-git]

Changed commit from 9868571 to ad57c6d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ad57c6d

and the same on dual_equivalence_class

[darijgr]

comment:34

Positive review by Travis who was standing over my shoulders and explaining what I should not do. :P

[sagetrac-git]

Changed commit from ad57c6d to 765cc78

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

765cc78

more crystal doc corrections

[darijgr]

comment:36

Couldn't resist fixing a few docstrings which made an iterator sound like it was a list and lists pretend to be iterators. Can you review this last bit, Travis? Thanks!

[tscrim]

comment:37

NP.

[anneschilling]

comment:38

For your coloring scheme, why don't you do it with a dictionary rather than the long list of if statements?

Anne

[sagetrac-git]

Changed commit from 765cc78 to 7abfd44

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

7abfd44

Changing to a dict for coloring and adding option to passing a list or dict.

[sagetrac-git]

Changed commit from 7abfd44 to 09320d9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a15b92f	Fix minor typo.
c500bfa	Make Sandpiles copyable
e4c701d	Implement GenericGraph.__copy__
3497edd	Merge branch 'u/vbraun/ticket/18032' of trac.sagemath.org:sage into public/crystals/dual_equivalence-18050
09320d9	Implementing a custom cache for the DEG. Marked a test as long.

[tscrim]

comment:41

That's a much better method to get the colors. I also pulled in #18032 because we needed to get immutable copies of the graph so I could write a custom cache which does not regenerate the graph when we only want a different coloring.

I also marked a test as long since it took nearly 20s on my computer.

Someone check my changes please.

[tscrim]

Dependencies: #18032

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7594b95

Simplifying the copying.

[sagetrac-git]

Changed commit from 09320d9 to 7594b95

[vbraun]

Changed branch from public/crystals/dual_equivalence-18050 to 7594b95