#26099 closed enhancement (fixed)
trim lattices
Reported by:  Frédéric Chapoton  Owned by:  

Priority:  minor  Milestone:  sage8.5 
Component:  combinatorics  Keywords:  
Cc:  Jori Mäntysalo  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  97ad922 (Commits, GitHub, GitLab)  Commit:  97ad92209130b6328a9042f96e40897af0e583db 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch adds is_trim()
to finite lattices.
Change History (23)
comment:1 Changed 4 years ago by
Branch:  → u/chapoton/26099 

Status:  new → needs_review 
comment:2 Changed 4 years ago by
Commit:  → 72846f5d843babe368c4862684d106dc3343230a 

comment:3 Changed 4 years ago by
Status:  needs_review → needs_work 

All other functions always returns a pair when certificate=True
, i.e.
x.foo() == x.foo(certificate=True)[0]
Change to this convention is possible, but should be discussed in sagedevel.
I suppose this also conflicts with #26095 because of a crosslink.
comment:4 Changed 4 years ago by
Commit:  72846f5d843babe368c4862684d106dc3343230a → 0490414339d1dcc004cb6a51e80e8f5e4d76d8fe 

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

comment:5 Changed 4 years ago by
done. For the conflict, I will just rebase the branch here when needed.
comment:6 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:7 Changed 4 years ago by
Commit:  0490414339d1dcc004cb6a51e80e8f5e4d76d8fe → 5ae834d5976231e024e5f2e82767f551cf3436f3 

Branch pushed to git repo; I updated commit sha1. New commits:
5ae834d  fix doctest in 26099

comment:8 Changed 4 years ago by
Reviewers:  → Jori Mäntysalo 

comment:9 Changed 4 years ago by
Status:  needs_review → positive_review 

OK.
(References should go to the master bibliography file, but that can be corrected later.)
comment:10 followup: 11 Changed 4 years ago by
A question still: The paper you refers says that a trim lattice must have a chain of maximum length having only left modular elements. The code seems to search a maximal chain having only left modular elements. So is the code sufficient?
comment:11 followup: 12 Changed 4 years ago by
Replying to jmantysalo:
A question still: The paper you refers says that a trim lattice must have a chain of maximum length having only left modular elements. The code seems to search a maximal chain having only left modular elements. So is the code sufficient?
Right. I am also using a result of https://arxiv.org/abs/1712.10123, saying that in a trim lattice, left modular elements are exactly the elements that belong to the spine (union of all chains of maximum length).
comment:12 Changed 4 years ago by
Replying to chapoton:
Replying to jmantysalo:
A question still: The paper you refers says that a trim lattice must have a chain of maximum length having only left modular elements. The code seems to search a maximal chain having only left modular elements. So is the code sufficient?
Right. I am also using a result of https://arxiv.org/abs/1712.10123, saying that in a trim lattice, left modular elements are exactly the elements that belong to the spine (union of all chains of maximum length).
But just this is what I am saying. You only need to check one chain of a maximum cardinality, not all of them. But your code does not do that, it tries to found some maximal chain, not necessarily of the max cardinality.
comment:13 followup: 14 Changed 4 years ago by
Status:  positive_review → needs_work 

Ha. Indeed. So this needs work. Let us keep this aside for some time, I have more urgent business right now.
comment:14 Changed 4 years ago by
Replying to chapoton:
Ha. Indeed. So this needs work. Let us keep this aside for some time, I have more urgent business right now.
OK. Could this be just
self.is_extremal() and all(self.is_left_modular_element(e) for e in self.height(certificate=True)[1])
?
comment:15 Changed 4 years ago by
Commit:  5ae834d5976231e024e5f2e82767f551cf3436f3 → fb3ed7370e1afbc5f5173440e2c6431482f4dc6b 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
fb3ed73  adding a method to test if a lattice is trim

comment:16 Changed 4 years ago by
Here is a new tentative, along the lines of your proposal. I did compare the timings with the corrected version of my code, and they were very similar. So I kept the simplest.
comment:17 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:18 Changed 4 years ago by
Description:  modified (diff) 

Status:  needs_review → positive_review 
OK.
comment:20 Changed 4 years ago by
Commit:  fb3ed7370e1afbc5f5173440e2c6431482f4dc6b → 97ad92209130b6328a9042f96e40897af0e583db 

Branch pushed to git repo; I updated commit sha1. New commits:
97ad922  Merge branch 'u/chapoton/26099' in 8.4.rc0

comment:21 Changed 4 years ago by
Status:  needs_work → positive_review 

trivial rebase, I am setting back to positive
comment:22 Changed 4 years ago by
Branch:  u/chapoton/26099 → 97ad92209130b6328a9042f96e40897af0e583db 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:23 Changed 4 years ago by
Milestone:  sage8.4 → sage8.5 

This should be retargeted for 8.5.
Branch pushed to git repo; I updated commit sha1. New commits:
adding a method to test if a lattice is trim