Opened 8 years ago

Last modified 7 years ago

#15272 needs_work enhancement

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

Reported by: vittucek Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: nthiery, bump, tscrim, aschilling Merged in:
Authors: Vít Tuček Reviewers:
Report Upstream: N/A Work issues:
Branch: u/vittucek/ticket/15272 (Commits, GitHub, GitLab) Commit: 64ea7c8216c4d0eb5cc39a648a629d4dd79ad5b7
Dependencies: Stopgaps:

Status badges

Description (last modified by vittucek)

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).

Attachments (1)

trac_15272_parabolic_bruhat_posets.patch (7.3 KB) - added by vittucek 8 years ago.

Download all attachments as: .zip

Change History (18)

Changed 8 years ago by vittucek

comment:1 Changed 8 years ago by vittucek

  • Authors set to Vít Tuček
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 8 years ago by vittucek

  • Branch set to u/vittucek/ticket/15272
  • Created changed from 10/12/13 21:52:36 to 10/12/13 21:52:36
  • Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52

comment:4 Changed 8 years ago by vittucek

  • Cc nthiery bump added
  • Commit set to 472c0908fba197fe9bb73742caab1ebfcde27b53
  • Description modified (diff)
  • Summary changed from Bruhat posets and Bruhat graphs for parabolic subgroups to Bruhat posets and Bruhat graphs for parabolic subgroups of finite Weyl groups

New commits:

7bb7c3bDecorate ClassicalWeylSubgroup.simple_reflections() with @cached_method.
6db7b6dFirst version of minimal coset representatives.
472c090Add parabolic minimal_coset_representatives, bruhat_graph and bruhat_poset

comment:5 Changed 8 years ago by tscrim

  • Cc tscrim aschilling added

comment:6 Changed 8 years ago by git

  • Commit changed from 472c0908fba197fe9bb73742caab1ebfcde27b53 to 92888b345acb3f6726c1d38ab16d4f1366fbb757

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

860f635Edge labels and other improvements in bruhat_graph
92888b3Raise NotImplementedError in minimal_representatives for infinite W

comment:7 follow-up: Changed 8 years ago by darij

  • Branch changed from u/vittucek/ticket/15272 to public/combinat/15272
  • Commit changed from 92888b345acb3f6726c1d38ab16d4f1366fbb757 to 1b1220d530e96cbfaf0927c539475327891e027d

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:

1b1220dmanual merge commit due to conflict with develop

comment:8 Changed 8 years ago by darij

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?

comment:9 follow-up: Changed 8 years ago by darij

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.)

comment:10 Changed 8 years ago by tscrim

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

comment:11 Changed 8 years ago by vittucek

  • Branch changed from public/combinat/15272 to u/vittucek/ticket/15272
  • Modified changed from 03/26/14 02:36:52 to 03/26/14 02:36:52

comment:12 in reply to: ↑ 7 Changed 8 years ago by vittucek

  • Commit changed from 1b1220d530e96cbfaf0927c539475327891e027d to b1e25e678525b169df881ef8312ecf30e64d3adf

Replying to darij:

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:

b1e25e6Performance enhancement in bruhat_graph

comment:13 Changed 8 years ago by git

  • Commit changed from b1e25e678525b169df881ef8312ecf30e64d3adf to 64ea7c8216c4d0eb5cc39a648a629d4dd79ad5b7

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

64ea7c8Bugfix: FiniteFamily is not a dictionary!

comment:14 in reply to: ↑ 9 Changed 8 years ago by vittucek

Replying to darij:

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.

comment:15 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:17 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply

Note: See TracTickets for help on using tickets.