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:  sage6.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: 
Description (last modified by )
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)
Change History (18)
Changed 8 years ago by
comment:1 Changed 8 years ago by
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 8 years ago by
 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
 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
comment:5 Changed 8 years ago by
 Cc tscrim aschilling added
comment:6 Changed 8 years ago by
 Commit changed from 472c0908fba197fe9bb73742caab1ebfcde27b53 to 92888b345acb3f6726c1d38ab16d4f1366fbb757
comment:7 followup: ↓ 12 Changed 8 years ago by
 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:
1b1220d  manual merge commit due to conflict with develop

comment:8 Changed 8 years ago by
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 followup: ↓ 14 Changed 8 years ago by
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
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
 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
 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 shortcircuiting. 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

comment:13 Changed 8 years ago by
 Commit changed from b1e25e678525b169df881ef8312ecf30e64d3adf to 64ea7c8216c4d0eb5cc39a648a629d4dd79ad5b7
Branch pushed to git repo; I updated commit sha1. New commits:
64ea7c8  Bugfix: FiniteFamily is not a dictionary!

comment:14 in reply to: ↑ 9 Changed 8 years ago by
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
 Milestone changed from sage6.2 to sage6.3
comment:16 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
New commits:
Decorate ClassicalWeylSubgroup.simple_reflections() with @cached_method.
First version of minimal coset representatives.
Add parabolic minimal_coset_representatives, bruhat_graph and bruhat_poset