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:  sage6.8 
Component:  combinatorics  Keywords:  
Cc:  tscrim, darij, sagecombinat  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: 
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 builtin 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
 Cc darij sagecombinat added
comment:2 Changed 6 years ago by
 Branch set to u/jonathan.judge/improve_cartan_type_recognition
comment:3 Changed 6 years ago by
 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)
toGenericGraph.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 fromfind_cartan_type_from_matrix
. It might make sense to turn this list into a function of n somewhere reasonable.
New commits:
d8d1685  Initial commit of changes

comment:4 Changed 6 years ago by
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.
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):
This is a slight variation than what is indicated on the ticket since
indecomposable_blocks
currently works by using theconnected_components
ofDiGraph
, so it avoids creating intermediary objects.