Opened 6 years ago

Last modified 6 years ago

#18744 new enhancement

Improve Cartan Type Recognition

Reported by: jonathan.judge Owned by:
Priority: major Milestone: sage-6.8
Component: combinatorics Keywords:
Cc: tscrim, darij, sage-combinat Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/jonathan.judge/improve_cartan_type_recognition (Commits, GitHub, GitLab) Commit: d8d1685ebc7dd76645a0172b7ecb65e5037119e7
Dependencies: Stopgaps:

Status badges

Description

This ticket is to improve Cartan type recognition when constructing Cartan matrices.

Specifically, when constructing a CartanMatrix from a Matrix or from a list of lists, CartanMatrix applies the function find_cartan_type_from_matrix. This function tests against Cartan matrices coming from built-in finite and affine CartanTypes. Currently, it does not detect Cartan types for relabellings of (Dynkin diagrams of) indecomposable Cartan matrices, nor does it detect reducible Cartan types for decomposable Cartan matrices. Improving the automatic detection of Cartan types is helpful when creating Cartan matrices on the fly, which in turn is useful for #18000.

After some preliminary analysis, it looks like the bulk of the work here can be accomplished by using the indecomposable_blocks method added to CartanMatrix in #18645, as well as the is_isomorphic method of the GenericGraph class (of which DynkinDiagram is a child class).

Change History (4)

comment:1 Changed 6 years ago by tscrim

  • Cc darij sage-combinat added

I propose to do the type checking only on the Dynkin diagram since there are good algorithms for checking digraph isomorphism (as indicated on the ticket):

sage: G = DiGraph([[1,2],[2,3],[3,1]])
sage: H = DiGraph([[0,-1],[-1,-2],[-2,0]])
sage: G.is_isomorphic(H, certify=True)
(True, {1: -2, 2: 0, 3: -1})

This is a slight variation than what is indicated on the ticket since indecomposable_blocks currently works by using the connected_components of DiGraph, so it avoids creating intermediary objects.

comment:2 Changed 6 years ago by jonathan.judge

  • Branch set to u/jonathan.judge/improve_cartan_type_recognition

comment:3 Changed 6 years ago by jonathan.judge

  • Commit set to d8d1685ebc7dd76645a0172b7ecb65e5037119e7

I just committed some initial work.

There are a few things I'm not happy about at the moment:

  • the change on line 18772 of generic_graph.py from G.relabel(return_map=True) to GenericGraph.relabel(G,return_map=True) was made due to the conflicting definition of the relabel function in DynkinDiagram. I tried to get around it by converting DynkinDiagrams to DiGraphs, but somehow I couldn't make it work. If there's a better way, please let me know.
  • there's some index set weirdness that I got around in finite type as on line 275 of cartan_matrix.py, but it feels hacky and I would like a better solution.
  • the variable test consisting of a list of Cartan types to test against is copied from find_cartan_type_from_matrix. It might make sense to turn this list into a function of n somewhere reasonable.

New commits:

d8d1685Initial commit of changes
Last edited 6 years ago by jonathan.judge (previous) (diff)

comment:4 Changed 6 years ago by tscrim

I think we should base this over #17798 since I had mucked around with the CartanMatrix constructor, which might fix the index set issue. If not, then I can look into it in more detail. I also don't like the change needed to get the relabel to work. Let me know when you're ready for me to take an deeper look into things here.

Note: See TracTickets for help on using tickets.