Bruhat posets and Bruhat graphs for parabolic subgroups of finite Weyl groups

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

This patch adds method minimal_representatives and extends the functionality of bruhat_poset and bruhat_graphs.

Let W be a finite Weyl group and let W_S be the subgroup of W generated by reflections associated with a subset S of simple roots. Then the cosets W / W_S have unique representatives of minimal length which are ordered by the Bruhat order of W. Similarly for W_S \ W. These poset structures appear in many places, e.g. intersection cohomology of generalized flag varieties or nilpotent Lie algebra cohomology.

This patch adds a parameters index_set (= S), crossed_nodes and side (left / right).

CC: @nthiery @dwbump @tscrim @anneschilling

Component: combinatorics

Author: Vít Tuček

Branch/Commit: u/vittucek/ticket/15272 @ 64ea7c8

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

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

comment:1

Attachment: trac_15272_parabolic_bruhat_posets.patch.gz

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

Author: Vít Tuček

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

Branch: u/vittucek/ticket/15272

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

Description changed:

--- 
+++ 
@@ -1,13 +1,5 @@
-This patch extends the functionality of bruhat_poset and introduces new parabolic_bruhat_graph for finite Weyl groups. 
+This patch adds method minimal_representatives and extends the functionality of bruhat_poset and bruhat_graphs.

 Let W be a finite Weyl group and let W_S be the subgroup of W generated by reflections associated with a subset S of simple roots. Then the cosets W / W_S have unique representatives of minimal length which are ordered by the Bruhat order of W. Similarly for W_S \ W. These poset structures appear in many places, e.g. intersection cohomology of generalized flag varieties or nilpotent Lie algebra cohomology.

-This patch adds a parameters index_set (= S) and side (left / right).
-
-
----
-
-
-Introducing parabolic_bruhat_graph is ugly. Ideally, one would just extend the existing bruhat_graph. However, this method is based upon bruhat_interval which belongs to categories/coxeter_groups.py 
-
-I was unsure where to put the code, which I haven't written yet nor which I need  in the foreseeable future anyway. Since it seems that the best course of action would be to implement class (or category?) for parabolic subroot systems / groups I think that one more method for Weyl group is not much of an issue.
+This patch adds a parameters index_set (= S), crossed_nodes and side (left / right).

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

Commit: 472c090

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

New commits:

7bb7c3b	Decorate ClassicalWeylSubgroup.simple_reflections() with @cached_method.
6db7b6d	First version of minimal coset representatives.
472c090	Add parabolic minimal_coset_representatives, bruhat_graph and bruhat_poset

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 472c090 to 92888b3

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

860f635	Edge labels and other improvements in bruhat_graph
92888b3	Raise NotImplementedError in minimal_representatives for infinite W

[darijgr]

comment:7

There is a merge conflict with develop:

        x = x.coset_representative(index_set,side)
        y = y.coset_representative(index_set,side)
        g = self.bruhat_poset(index_set, crossed_nodes, side, facade=True).interval(x,y)
        ref = self.reflections()
        d = {}
        for x in g:
<<<<<<< HEAD
            d[x] = [y for y in g if x.length() < y.length() and x*y.inverse() in ref]
=======
            d[x] = {}
            for y in g:
                if side == "right":
                    r = y*x.inverse()
                else:
                    r = x.inverse()*y
                if x.length() < y.length() and ref.has_key(r):
                    d[x][y] = r
>>>>>>> 92888b345acb3f6726c1d38ab16d4f1366fbb757
        return DiGraph(d)

I'm pushing a branch (warning: branch change!) in which I resolve this in favor of your patch's version (the longer one, with the "for y in g" loop and the dictionary rather than the list). If this is wrong, please let me know.

---

New commits:

1b1220d

manual merge commit due to conflict with develop

[darijgr]

Changed commit from 92888b3 to 1b1220d

[darijgr]

Changed branch from u/vittucek/ticket/15272 to public/combinat/15272

[darijgr]

comment:8

That said, what do you think about pulling the if side == "right" check outside of the loop, so as to not repeat it over and over?

[darijgr]

comment:9

Oh, and also the conflict was because some other patch replaced ref.has_key(...) by ... in ref. Maybe do the same in your code? (I don't know what the difference is; it just sounds like a logical thing to do.)

[tscrim]

comment:10

The has_key is being deprecated (removed?) in python3 in favor of the in syntax (which I believe is faster...?). Also I agree with Darij since this loop is so small, I'd pull the side == "right" statement outside as:

if side == "right":
    for y in g:
        r = y*x.inverse()
    if x.length() < y.length() and r in ref:
        d[x][y] = r
else:
    for y in g:
        r = x.inverse()*y
    if x.length() < y.length() and r in ref:
        d[x][y] = r

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

Changed branch from public/combinat/15272 to u/vittucek/ticket/15272

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

comment:12

Replying to @darijgr:

There is a merge conflict with develop:

        x = x.coset_representative(index_set,side)
        y = y.coset_representative(index_set,side)
        g = self.bruhat_poset(index_set, crossed_nodes, side, facade=True).interval(x,y)
        ref = self.reflections()
        d = {}
        for x in g:
<<<<<<< HEAD
            d[x] = [y for y in g if x.length() < y.length() and x*y.inverse() in ref]
=======
            d[x] = {}
            for y in g:
                if side == "right":
                    r = y*x.inverse()
                else:
                    r = x.inverse()*y
                if x.length() < y.length() and ref.has_key(r):
                    d[x][y] = r
>>>>>>> 92888b345acb3f6726c1d38ab16d4f1366fbb757
        return DiGraph(d)

I'm pushing a branch (warning: branch change!) in which I resolve this in favor of your patch's version (the longer one, with the "for y in g" loop and the dictionary rather than the list). If this is wrong, please let me know.

---

Thanks! I've made the change you've requested (and moreover I've switched the order of tests to benefit from short-circuiting. I didn't know how to add the patch on top of your branch (insufficient permissions?) so I just went with what sage -dev push suggested. I hope that's fine.

---

New commits:

b1e25e6

Performance enhancement in bruhat_graph

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

Changed commit from 1b1220d to b1e25e6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b1e25e6 to 64ea7c8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

64ea7c8

Bugfix: FiniteFamily is not a dictionary!

[fe60a72e-b3d0-4317-856b-4536ec0e4b8d]

comment:14

Replying to @darijgr:

Oh, and also the conflict was because some other patch replaced ref.has_key(...) by ... in ref. Maybe do the same in your code? (I don't know what the difference is; it just sounds like a logical thing to do.)

Ehm. I have done this change too hastily. As it turns out ref is not a dictionary but a FiniteFamily which means that its __contains__ method looks at the values. It's __contains__ method was changed #15784 to use in in favor of has_key.

[fchapoton]

comment:17

does not apply