Opened 6 years ago
Closed 6 years ago
#21002 closed enhancement (fixed)
LatticePoset: certificates for nonsemimodularity
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  combinatorics  Keywords:  
Cc:  kdilks, tscrim  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  c059d46 (Commits, GitHub, GitLab)  Commit:  c059d46ef3a9f7150f988fc7889dc39ef7defd95 
Dependencies:  Stopgaps: 
Description (last modified by )
Add a certificate
option to the functions checking if a lattice is semimodular.
Change History (11)
comment:1 Changed 6 years ago by
 Cc kdilks added
 Status changed from new to needs_info
comment:2 Changed 6 years ago by
 Branch set to u/jmantysalo/latticeposet__certificates_for_non__semi_modularity_and_non_distributivity
comment:3 Changed 6 years ago by
 Cc tscrim added
 Commit set to 10cb3ca6bcfb3d79793200b9f1def5be584a8e46
 Description modified (diff)
 Milestone changed from sagefeature to sage7.3
 Status changed from needs_info to needs_review
 Summary changed from LatticePoset: certificates for non[semi]modularity and nondistributivity to LatticePoset: certificates for nonsemimodularity
I thinked about this, and here is first part.
First, this is faster for almost all cases. But for small lattices with already computed meet, join and rank function this is slower. However, the speedup for, say, BooleanLattice(10)
is big. With current code the time to check semimodularity is 4,9 seconds for first time and 0,6 seconds for second time. With this patch it drops to 0,1 seconds.
Second, this adds a certificate
option.
I thinked this, and I guess we should use this bydefinition certificate, and later implement isomoprhic_sublattices()
.
I will put this to needs_review and later try to do something similar to is_modular()
and is_distributive()
.
New commits:
10cb3ca  Modifications to semimodularity tests.

comment:5 Changed 6 years ago by
Just pinging... Nothing very complicated here.
comment:6 followup: ↓ 9 Changed 6 years ago by
Even though it's a "hidden" function, I don't think the method in hasse_diagram.py
should be called is_semimodular()
if it's not in some way return a boolean (either directly, or as part of a tuple along with certificate).
comment:7 Changed 6 years ago by
 Commit changed from 10cb3ca6bcfb3d79793200b9f1def5be584a8e46 to c9a365cb5bd5fd0e4d8916650e219c35cebc64d2
Branch pushed to git repo; I updated commit sha1. New commits:
c9a365c  Change internal function name.

comment:8 Changed 6 years ago by
 Commit changed from c9a365cb5bd5fd0e4d8916650e219c35cebc64d2 to c059d46ef3a9f7150f988fc7889dc39ef7defd95
Branch pushed to git repo; I updated commit sha1. New commits:
c059d46  Forgot *lower* semimodular.

comment:9 in reply to: ↑ 6 Changed 6 years ago by
Replying to kdilks:
Even though it's a "hidden" function, I don't think the method in
hasse_diagram.py
should be calledis_semimodular()
if it's not in some way return a boolean (either directly, or as part of a tuple along with certificate).
True. Changed that.
comment:10 Changed 6 years ago by
 Reviewers set to Kevin Dilks
 Status changed from needs_review to positive_review
comment:11 Changed 6 years ago by
 Branch changed from u/jmantysalo/latticeposet__certificates_for_non__semi_modularity_and_non_distributivity to c059d46ef3a9f7150f988fc7889dc39ef7defd95
 Resolution set to fixed
 Status changed from positive_review to closed
Kevin: First part is #20980, but a question about interface part:
What should be the certificate? I.e. a sublattice, a list of five elements of the sublattice, or list of three elements violating the defining property? Or a choise between those?