Implementation of the SubwordComplex as defined by Knutson and Miller

[stumpc5]

This patch provides an implementation of the subword complex:

Fix a Coxeter system (W,S). Let Q = be a finite word in S and pi in W.

The subword complex Delta(Q,pi) is then defined to be the simplicial complex with vertices being {0,...,n-1}, (n = len(Q), one vertex for each letter in Q) and with facets given by all (indices of) subwords Q' of Q for which Q\Q' is a reduced expression for pi.

    sage: W = CoxeterGroup(['A',2],index_set=[1,2])
    sage: w = W.from_reduced_word([1,2,1])
    sage: C = SubwordComplex([2,1,2,1,2],w); C
    Subword complex of type ['A', 2] for Q = [2, 1, 2, 1, 2] and pi = 121
    sage: C.facets()
    {(1, 2), (3, 4), (0, 4), (2, 3), (0, 1)}

Component: combinatorics

Keywords: subword complex, simplicial complex

Author: Christian Stump

Branch/Commit: 17518c1

Reviewer: Frédéric Chapoton

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

[stumpc5]

Author: Christian Stump

[stumpc5]

Changed keywords from none to subword complex, simplicial complex

[stumpc5]

Dependencies: 11187, 11122

[stumpc5]

Changed dependencies from 11187, 11122 to #11187, #11122

[stumpc5]

Changed dependencies from #11187, #11122 to #11122

[fchapoton]

Changed dependencies from #11122 to #12774

[stumpc5]

comment:7

Replying to @fchapoton:

Okay, I must confess that I tend to not finish implementations once the patch does what I want it to do...

The dependencies of this patch must (unfortunately) inherit as well the dependencies of #11122. This is to say that this patch actually relies on many things implemented in #11187.

I would be very, very glad if anyone would finally start reviewing the universal cyclotomic field, #8327 on which #11187 depends (I would first need to rebase it, and make sure that the trac version is updated to the newest version on the combinat queue).

Cheers, Christian

[stumpc5]

Changed dependencies from #12774 to #11187, #12774

[stumpc5]

Attachment: trac_11010-subword_complex-cs.patch.gz

[fchapoton]

Branch: u/chapoton/11010

[fchapoton]

comment:10

I have made a git branch. It does not work: runs into an infinite recursion because of #15456.

---

New commits:

3b8df81	trac_11010-subword_complex-cs.patch
a525fdc	trac #11010 code clean-up

[fchapoton]

Commit: a525fdc

[fchapoton]

comment:11

The code needs to be 100% doctested. Some empty methods should be removed.

[fchapoton]

Work Issues: coverage

[fchapoton]

Changed dependencies from #11187, #12774 to #11187, #12774, #15456

[tscrim]

comment:70

Does the plotting also work for type C, being that it is the dual of type B (and we are dealing with Cartan types)?

[stumpc5]

comment:71

I am rather confused now:

• First Sage start

sage: W = CoxeterGroup(['B',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['B', 4]
sage: W = CoxeterGroup(['C',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['B', 4]

• Second Sage start

sage: W = CoxeterGroup(['C',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['C', 4]
sage: W = CoxeterGroup(['B',4])
sage: W.coxeter_matrix().coxeter_type()
Coxeter type of ['C', 4]

In particular, the root systems W.roots() are not correct in the two second calls of CoxeterGroup.

Also, the plotting now assumes that the first index is the type B/C special one. This is, it is expected that

sage: s0 = W.simple_reflection(W.index-set()[0])
sage: s1 = W.simple_reflection(W.index-set()[1])
sage: (s0*s1).order()
4

I doubt that this is correct in the current implementation of Coxeter groups where the last index is expected to be special. If so, I will add some magic to figure out the proper labelling...

[tscrim]

comment:72

The first issue is the result of my quick hacking to get something working. The Coxeter matrices are equal for the Cartan types B and C, and the Coxeter matrix is the information passed to the UniqueRepresentation cache. There are a number of ways to go moving forward, but I think that deserves its own separate ticket.

For the second issue, yes, you are correct. The n-1 and n nodes have the order 4 relation between them, as this agrees with the corresponding B/C Cartan types (and the Coxeter matrix). You are welcome to relabel the Coxeter type, which should work, or go to the Coxeter graph and find the edge label4ed by 4 and use those nodes. Personally, I would use the latter option since it is independent of the labeling.

[stumpc5]

comment:73

I also have the problem that the plot only allows irreducible types. When playing with reducible types, I got to the types B vs. G bug in #19830...

[stumpc5]

Changed branch from u/chapoton/11010 to u/stumpc5/11010

[fchapoton]

comment:76

Is this "needs_review" ?

---

New commits:

4864a64	Merge branch '11010-new' into u/stumpc5/11010-new
7722489	Merge branch 'u/chapoton/11010' of git://trac.sagemath.org/sage into u/stumpc5/11010-new
839b2e2	fixing the index set for the plot

[fchapoton]

Changed commit from 1b10c95 to 839b2e2

[stumpc5]

comment:77

Is this "needs_review" ?

Not quite, I wanted to add a few more doctests for the type B plotting with various indexing sets. But then saw that the indexing in CoxeterGroup is corrupted, see #19830. This is another issue, but I still want to add more examples/testing.

[sagetrac-git]

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

0f90c26

fixed another b/c bug + some cosmetics to the code

[sagetrac-git]

Changed commit from 839b2e2 to 0f90c26

[sagetrac-git]

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

e8e160c

fixed a docstring and adding one more test

[sagetrac-git]

Changed commit from 0f90c26 to e8e160c

[fchapoton]

Changed commit from e8e160c to 17518c1

[fchapoton]

comment:81

ok, good enough for me.

I have made two minor doc changes, and now set this again to positive review.

Any further changes will have to be in another ticket.

---

New commits:

17518c1

trac #11010 two details

[fchapoton]

Changed branch from u/stumpc5/11010 to u/chapoton/11010

[vbraun]

Changed branch from u/chapoton/11010 to 17518c1