Extend bruhat graphs

[thecaligarmo]

Right now we can only get the Bruhat graph of Weyl groups even though we can do the same thing for Coxeter Groups. I plan on moving bruhat_graph from the WeylGroups class in combinat/root_system to the category of Coxeter groups. This will keep WeylGroup having the method, but expand it to Coxter groups.

Additionally, it would be natural to not require two elements to find a the graph between them. So instead, if the group is finite, we'll allow the calling of bruhat_graph() which will bring back the entire graph.

CC: @nthiery @tscrim @fchapoton

Component: combinatorics

Keywords: sagedays86

Author: Aram Dermenjian

Branch/Commit: 33265f8

Reviewer: Travis Scrimshaw, Frédéric Chapoton

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

[thecaligarmo]

Changed keywords from none to sagedays86

[thecaligarmo]

Branch: u/aram.dermenjian/generalize_bruhat_graphs

[thecaligarmo]

comment:4

This should be ready for review.

---

New commits:

f64c494

Move bruhat_graph to Coxeter category

[thecaligarmo]

Commit: f64c494

[thecaligarmo]

Reviewer: nthiery,tscrim,chapoton

[thecaligarmo]

Changed author from aram.dermenjian to Aram Dermenjian

[thecaligarmo]

Changed reviewer from nthiery,tscrim,chapoton to Nicolas M. Thiéry,Travis Scrimshaw,Frédéric Chapoton

[thecaligarmo]

Changed reviewer from Nicolas M. Thiéry,Travis Scrimshaw,Frédéric Chapoton to none

[tscrim]

comment:7

Some comments:

-I think the extra doctests should not be in the block below saying :trac:`17744`, but above it.

• Instead of this complicated check for the long element and you already test self.is_finite(), so just do the default being the long element there. This is better locality of code.
• A better error message would be infinite groups must specify a maximal element.
• reflection_length needs a doctest.
• Even though it is slight code duplication, it would be faster (and probably cleaner) to use code similar to bruhat_interval. While this could be done on a separate ticket, I think it would be better to do this here and now.

[sagetrac-git]

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

edda1ff

Update doctests and error messaging

[sagetrac-git]

Changed commit from f64c494 to edda1ff

[sagetrac-git]

Changed commit from edda1ff to bea06ba

[sagetrac-git]

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

bea06ba

doc tests

[thecaligarmo]

comment:10

So all the above corrections have been made.

I didn't understand what you meant by replicating bruhat_interval in your last comment. Do you mean using a similar while loop in bruhat_group to find all potential additional chains? The issue here is that if the group is infinite we can't go through "all" the reflections to test things out. Hence why this method was used (and I kept it over from the current version). Unless you mean something different?

---

New commits:

edda1ff	Update doctests and error messaging
bea06ba	doc tests

[tscrim]

comment:11

Actually, looking into this a bit more, I think we should have bruhat_graph be constructed from the transitive closure of the digraph of the Bruhat cover relations. This way we would not have to look at what is a reflection and what is not.

So what I would do is start with a hidden method _bruhat_covers_digraph, which builds the digraph of cover relations by using code from bruhat_interval. Then bruhat_graph would return self._bruhat_covers_digraph(x,y).transitive_closure(). Furthermore, bruhat_poset could be lifted and generalized to return Poset(self._bruhat_covers_digraph(x,y), cover_relations=True, facade=facade).

I can do this is if you want me to.

[sagetrac-git]

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

d5875c1

Allow edge labels in Bruhat graph

[sagetrac-git]

Changed commit from bea06ba to d5875c1

[thecaligarmo]

comment:13

So one reason transitive closure isn't a good idea is because I'd like to keep track of the reflection used to make that transition (as added in my latest commit). Also, I'm not exactly sure how the transitive closure would work in this case. Do you want to do a run with the poset and if it works as expected I can merge the two with Bruhat graph? (Or you can add it into Bruhat graph directly if you'd prefer)

[tscrim]

Changed branch from u/aram.dermenjian/generalize_bruhat_graphs to public/combinat/extend_bruhat_graphs-22854

[tscrim]

Changed commit from d5875c1 to 33265f8

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:14

Actually, the transitive closure is too permissive as you can get differences that are products of reflections, which of course, are not always reflections. However, I was able to get a massive speed boost by sorting the bruhat_interval by length so we only have to do approx n^2 / 2 checks and not have to do the length checks each time.

I also added a bruhat_interval_poset, which goes slightly beyond the scope of the ticket but is in the spirit of it, instead of lifting up bruhat_poset to keep that reserved for the entire Bruhat order poset.

---

New commits:

9164839	Merge branch 'u/aram.dermenjian/generalize_bruhat_graphs' of git://trac.sagemath.org/sage into public/combinat/extend_bruhat_graphs-22854
33265f8	Add bruhat_interval_poset and speedup of bruhat_graph.

[tscrim]

comment:15

ping - Patchbot is (essentially) green.

[fchapoton]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton

[fchapoton]

comment:16

ok, let it be (though I do not like that "reflection length" is not just an alias).

[thecaligarmo]

comment:17

Looks good on my end too. I can always quickly alter reflection length to be an alias instead of a direct call if you'd prefer Chapoton. (I hadn't realised aliasing was possible) Just let me know and I'll quickly do it tonight.

[fchapoton]

comment:18

No, let us keep things as they are, no need to re-open the ticket for that.

[vbraun]

Changed branch from public/combinat/extend_bruhat_graphs-22854 to 33265f8