Opened 8 years ago

Closed 7 years ago

#15137 closed enhancement (fixed)

Implement right-angled Artin groups

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.3
Component: group theory Keywords: Artin group RAAG, days54, sd58
Cc: vbraun, mmarco Merged in:
Authors: Travis Scrimshaw Reviewers: Frédéric Chapoton, Miguel Marco
Report Upstream: N/A Work issues:
Branch: 473384d (Commits, GitHub, GitLab) Commit: 473384d5da5a387464e3ba66d6f2a5ef28bb3ee5
Dependencies: #15603 #15669 Stopgaps:

Status badges

Description (last modified by tscrim)

This patch implements Right-angled Artin groups (RAAG's for short, a.k.a. graph groups or partially commutative groups).

Attachments (1)

trac_15137-groups-ts.patch (14.4 KB) - added by tscrim 8 years ago.

Download all attachments as: .zip

Change History (32)

comment:1 Changed 8 years ago by tscrim

  • Status changed from new to needs_review

There is a TODO in that there isn't a good way to create a matrix over ZZ union oo. By default, it coerces into the infinity ring, and explicitly working over the symbolic ring, I couldn't get the equals check to work. I think we'd need a ring for a base ring union infinity as a default coercion.

comment:2 Changed 8 years ago by hthomas

Hi Travis--

It's a bit of a hack, but what about using -1 for infinity in the Coxeter matrix?

cheers,

Hugh

comment:3 Changed 8 years ago by tscrim

  • Description modified (diff)

That's a good idea. It has been done.

comment:4 follow-up: Changed 8 years ago by chapoton

Would it be possible to replace the symbolic ring (awful thing in my opinion) by the universal cyclotomic field (see my addon patch in #14816) ?

And how do you interact with #14816 (and also with #9290) ?

Last edited 8 years ago by chapoton (previous) (diff)

comment:5 in reply to: ↑ 4 Changed 8 years ago by tscrim

Replying to chapoton:

Would it be possible to replace the symbolic ring (awful thing in my opinion) by the universal cyclotomic field (see my addon patch in #14816) ?

I don't like the symbolic ring either, but I wan't quite sure before about how to make it work with the UCF. I'm thinking we could peel off the necessary portion of your addon patch in #14816 and put it with the Coxeter group code.

And how do you interact with #14816 (and also with #9290) ?

I didn't notice #9290, so shall we move the Coxeter group code there? I also haven't thought completely through yet how I want to interact with #14816 and Weyl groups of root systems.

comment:6 Changed 8 years ago by tscrim

  • Description modified (diff)
  • Keywords Coxeter removed
  • Summary changed from Implement general Coxeter groups and RAAGs to Implement right-angled Artin groups

I've split off the Coxeter portion to #9290 since that ticket already is for that. This ticket now focuses solely on a first implementation of RAAG's.

Changed 8 years ago by tscrim

comment:7 Changed 8 years ago by tscrim

  • Branch set to public/groups/15137-raags
  • Commit set to e8de01ffac34d7a9bd27a2b81fefe728fad1dbb1

New commits:

e8de01f#15137: Implement right-angled Artin groups and general Coxeter groups.

comment:8 Changed 8 years ago by tscrim

  • Keywords days54 added

comment:9 Changed 7 years ago by git

  • Commit changed from e8de01ffac34d7a9bd27a2b81fefe728fad1dbb1 to 0f6f1b49532de4b6a55310debeb0a1f0aa6df1ca

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

4d5091eMerge branch 'public/groups/15137-raags' of trac.sagemath.org:sage into public/groups/15137-raags
0f6f1b4Changed to use new immutable graph backend.

comment:10 Changed 7 years ago by tscrim

  • Cc vbraun mmarco added
  • Dependencies set to #15603

Because I think they are a very interesting class of groups (and GAP doesn't have them :p), I'd appreciate a review.

comment:11 follow-up: Changed 7 years ago by mmarco

Would it make sense to inherit from FinitelyPresentedGroup?? Things like the Alexander matrix could be interesting to have.

comment:12 Changed 7 years ago by chapoton

1) the following does not work:

sage: G = RightAngledArtinGroup?(graphs.EmptyGraph?())

it should either fail more gracefully or succeed.

2) there is a typo "creaing"

3) maybe the string representation could use the string repr of the graph ? maybe instead of just the number of vertices ?

comment:13 in reply to: ↑ 11 Changed 7 years ago by tscrim

Replying to mmarco:

Would it make sense to inherit from FinitelyPresentedGroup?? Things like the Alexander matrix could be interesting to have.

I'm not sure. FinitelyPresentedGroup is a Gap group, this is implementation is pure python/Sage, and I don't know how to mix the two. There should be methods to construct the corresponding FP group, as well as the ability to pass this to Gap (as a FP group).

Replying to chapoton:

1) the following does not work:

sage: G = RightAngledArtinGroup??(graphs.EmptyGraph??())

it should either fail more gracefully or succeed.

Grrr...boarder cases; I'll fix this after I see what would be the most consistent behavior.

2) there is a typo "creaing"

Will fix.

3) maybe the string representation could use the string repr of the graph ? maybe instead of just the number of vertices ?

That would be better; will change.

comment:14 Changed 7 years ago by git

  • Commit changed from 0f6f1b49532de4b6a55310debeb0a1f0aa6df1ca to 7856bc45c5c3fd64a7303b7e4465b7add71ef7eb

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

7856bc4Made changes and expanded documentation.

comment:15 Changed 7 years ago by git

  • Commit changed from 7856bc45c5c3fd64a7303b7e4465b7add71ef7eb to 457f00d48a863dcf34eb93a95243d203ec7c69ad

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

457f00dAdded FP group and gap to raag.py.

comment:16 Changed 7 years ago by tscrim

I've added a quick way to create a FP group from a RAAG and fixed all of Frederic's comments (the failing was actually uncovered a bug in the graph code).

comment:17 Changed 7 years ago by git

  • Commit changed from 457f00d48a863dcf34eb93a95243d203ec7c69ad to 2dff54390f37ddca1021cf69c1c5a5a32b52074d

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

30d2132Merge branch 'develop' into public/groups/15137-raags
5b42e19Fixed complement for immutable graphs.
e2a498cFixed doctest output.
b6ed038trac #15623: Immutable graph backend for Posets
ee8c395Trac 15623: Let to_graph return an immutable graph
dcb8a0btrac #15623: rebase on 6.1.beta4
3531566trac #15623: Rebase on updated #15622
95cecd1trac #15623: Removing the hack from #15622, update a variable's name
898a8e6trac #15681: Name of immutable graphs
30dd8ddMerge branch 'u/ncohen/15681' into public/graphs/complement-15699

comment:18 Changed 7 years ago by tscrim

  • Dependencies changed from #15603 to #15603 #15669

comment:19 Changed 7 years ago by git

  • Commit changed from 2dff54390f37ddca1021cf69c1c5a5a32b52074d to 744dd52a2bcd661e96c2c4443c66eb690cc7b6d6

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

a784a50Merge branch 'develop' into public/groups/15137-raags
dae53afMerge branch 'develop' into ticket/15623
c5b6d59Re-insert a bit of code that had been erroneously deleted in the previous merge commit
81fc8a4Merge branch 'u/ncohen/15681' of trac.sagemath.org:sage into u/tscrim/15681
c393b58Merge branch 'public/graphs/complement-15699' of trac.sagemath.org:sage into public/graphs/complement-15669
744dd52Merge branch 'public/graphs/complement-15669' into public/groups/15137-raags

comment:20 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:21 Changed 7 years ago by git

  • Commit changed from 744dd52a2bcd661e96c2c4443c66eb690cc7b6d6 to 0f5b6c84a8f5af5794af5bb91816c344b30dfb5b

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

e1002a5Merge branch 'develop' into public/groups/15137-raags
0f5b6c8Merge branch 'develop' into public/groups/15137-raags

comment:22 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:23 Changed 7 years ago by git

  • Commit changed from 0f5b6c84a8f5af5794af5bb91816c344b30dfb5b to 86c8c872af6c1a1967b1f4045f13e4c3e0f482f6

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

b30ad29Merge branch 'public/groups/15137-raags' of trac.sagemath.org:sage into public/groups/15137-raags
6e6d0efFixing bad merge and added RAAG's to the catalog.
86c8c87Rewrote RAAG as Gap group and did some logic/pickling cleanup of FP groups.

comment:24 Changed 7 years ago by git

  • Commit changed from 86c8c872af6c1a1967b1f4045f13e4c3e0f482f6 to d78fc558eed8254313d1aac039e17eb8883cbca9

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

d78fc55Improving documentation from talking with Miguel.

comment:25 Changed 7 years ago by git

  • Commit changed from d78fc558eed8254313d1aac039e17eb8883cbca9 to ce328e86d829356b8a5d17270b0d615556a86780

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

ce328e8Removed non-ascii character.

comment:26 Changed 7 years ago by git

  • Commit changed from ce328e86d829356b8a5d17270b0d615556a86780 to 473384d5da5a387464e3ba66d6f2a5ef28bb3ee5

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

473384dFixed citation.

comment:27 Changed 7 years ago by mmarco

  • Status changed from needs_review to positive_review

Looks good.

comment:28 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

reviewer name

comment:29 Changed 7 years ago by tscrim

  • Reviewers set to Frédéric Chapoton, Miguel Marco
  • Status changed from needs_work to positive_review

comment:30 Changed 7 years ago by tscrim

  • Keywords sd58 added

comment:31 Changed 7 years ago by vbraun

  • Branch changed from public/groups/15137-raags to 473384d5da5a387464e3ba66d6f2a5ef28bb3ee5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.